princeza.cpp

Bài toán

Các lá sen nằm trên hệ tọa độ hai chiều. Một con ếch xuất phát từ lá sen thứ nhất, thực hiện liên tiếp các chỉ dẫn. Hỏi sau khi thực hiện hết các thao tác thì con ếch ở vị trí nào. 4 loại chỉ dẫn được ghi rõ ràng ở trong đề.

Độ phức tạp

O(m logn)

Code này của Nguyễn Tiến Trung Kiên

#include <stdio.h>

#include <set>

#include <algorithm>

using namespace std;

typedef pair<int, int> ii;

typedef pair<int, ii> triple;

typedef set<triple>::iterator sit_triple;

#define X first

#define Y second

int n, m;

set<triple> sa, sb;

ii a[1230997];

void jump_sa(sit_triple &it, sit_triple &jt, sit_triple zt){

    sa.erase(it);

    sb.erase(jt);

    it=zt;

    jt=sb.lower_bound(triple(zt->Y.X+zt->Y.Y, zt->Y));

}

void jump_sb(sit_triple &it, sit_triple &jt, sit_triple zt){

    sa.erase(it);

    sb.erase(jt);

    it=sa.lower_bound(triple(zt->Y.X-zt->Y.Y, zt->Y));

    jt=zt;

}

char s[1230997];

main(){

    char c; int i;

    scanf("%d%d", &n, &m);

    scanf("%s", s);

    for (i=1; i<=n; i++)

    scanf("%d%d", &a[i].X, &a[i].Y);

    for (i=1; i<=n; i++){

        sa.insert(triple(a[i].X-a[i].Y, ii(a[i].X, a[i].Y)));

        sb.insert(triple(a[i].X+a[i].Y, ii(a[i].X, a[i].Y)));

    }

    set<triple> :: iterator it = sa.lower_bound(triple(a[1].X-a[1].Y, a[1]));

    set<triple> :: iterator jt = sb.lower_bound(triple(a[1].X+a[1].Y, a[1]));

    set<triple> :: iterator zt;

    for (i=0; c=s[i]; i++){

        if (c=='A') { zt=it; zt++; if (zt!=sa.end() && zt->X==it->X) jump_sa(it, jt, zt); }

        if (c=='B') { zt=jt; zt++; if (zt!=sb.end() && zt->X==jt->X) jump_sb(it, jt, zt); }

        if (c=='C') if (jt!=sb.begin()) { zt=jt; zt--; if (zt->X==jt->X) jump_sb(it, jt, zt); }

        if (c=='D') if (it!=sa.begin()) { zt=it; zt--; if (zt->X==it->X) jump_sa(it, jt, zt); }

    }

    printf("%d %d\n", it->Y.X, it->Y.Y);

}

Nhận xét