Submission #964690

#	Time	Username	Problem	Language	Result	Execution time	Memory
964690		anango	Aliens (IOI07_aliens)	C++17	0 / 100	1 ms	596 KiB

aliens

#include <bits/stdc++.h>
#define int long long
using namespace std;

int n,orgx,orgy;
int query(int xa, int y) {
    if (xa>n || xa<=0 || y>n || y<=0) {
        return 0;
    }
    cout << "examine" <<" " << xa <<" " << y << endl;
    string x;
    cin >> x;
    if (x[0]=='t') {
        return 1;
    }
    return 0;
}
void answer(int x, int y) {
    cout << "solution" <<" " << x <<" " << y << endl;
}


signed main() {
    cin >> n >> orgx >> orgy;
    int maxn=2000000000;
    int l=orgy;
    int r=-1;
    for (int i=0; i<33; i++) {
        if (query(orgx,orgy+(1<<i))==0) {
            r=orgy+(1<<i);
            break;
        }
    }
    while (l<r) {
        int m=(l+r)/2;
        int an=query(orgx,m);
        if (an==1) {
            l=m+1;
            r=r;
        }
        else {
            l=l;
            r=m;
        }
    }
    int fws=l; //first ungrassed square downwards
    l=orgy;
    r=-1;
    for (int i=0; i<33; i++) {
        if (query(orgx,orgy-(1<<i))==0) {
            r=orgy-(1<<i);
            break;
        }
    }
    swap(l,r);
    while (l<r) {
        int m=(l+r)/2;
        int an=query(orgx,m);
        if (an==0) {
            l=m+1;
            r=r;
        }
        else {
            l=l;
            r=m;
        }
    }
    int fbs=l; //first ungrassed square downwards
    int gsize=fws-fbs;
    
     l=orgx;
     r=-1;
    for (int i=0; i<33; i++) {
        if (query(orgx+(1<<i),orgy)==0) {
            r=orgx+(1<<i);
            break;
        }
    }
    while (l<r) {
        int m=(l+r)/2;
        int an=query(m,orgy);
        if (an==1) {
            l=m+1;
            r=r;
        }
        else {
            l=l;
            r=m;
        }
    }
    int dws=l; //first ungrassed square left
    l=orgx;
    r=-1;
    for (int i=0; i<33; i++) {
        if (query(orgx-(1<<i),orgy)==0) {
            r=orgx-(1<<i);
            break;
        }
    }
    swap(l,r);
    while (l<r) {
        int m=(l+r)/2;
        int an=query(m,orgy);
        if (an==0) {
            l=m+1;
            r=r;
        }
        else {
            l=l;
            r=m;
        }
    }
    int dbs=l; //first ungrassed square left
    int size2=dws-dbs;
    int cbotx = gsize/2+dbs;
    int cboty = fbs+gsize/2;
    //cout << "center of each square " << cbotx <<" " << cboty << " "<< gsize << endl;
    assert(gsize==size2);
    orgx=cbotx;
    orgy=cboty;
    int ri=0;
    for (int i=1; i<4; i++) {
        int t=query(orgx+2*gsize*i, orgy);
        if (t==0) {
            ri=i-1; //the number of grassed ones to the right of given cell
            break;
        }
    }
    int li=0;
    for (int i=1; i<4; i++) {
        int t=query(orgx-2*gsize*i, orgy);
        if (t==0) {
            li=i-1; //the number of grassed ones to the left of given cell
            break;
        }
    }
    int ui=0;
    for (int i=1; i<4; i++) {
        int t=query(orgx, orgy+2*gsize*i);
        if (t==0) {
            ui=i-1; //the number of grassed ones to the right of given cell
            break;
        }
    }
    int di=0;
    for (int i=1; i<4; i++) {
        int t=query(orgx, orgy-2*gsize*i);
        if (t==0) {
            di=i-1; //the number of grassed ones to the left of given cell
            break;
        }
    }
    int coordx=0;
    int coordy=0;
    map<vector<int>,pair<int,int>> M;
    for (int i=0; i<5; i++) {
        for (int j=0; j<5; j++) {
            int ui=0;
            int di=0;
            int ri=0;
            int li=0;
            if ((i+j)%2==1) {
                continue;
            }
            for (int t=j+1; t<5; t++) {
                if ((i+t)%2==0) {
                    ui++;
                }
            }
            for (int t=0; t<j; t++) {
                if ((i+t)%2==0) {
                    di++;
                }
            }
            swap(i,j);
            for (int t=j+1; t<5; t++) {
                if ((i+t)%2==0) {
                    ri++;
                }
            }
            for (int t=0; t<j; t++) {
                if ((i+t)%2==0) {
                    li++;
                }
            }
            swap(i,j);
            M[{ui,di,li,ri}] = {i,j};
        }
    }
    assert(M.count({ui,di,li,ri}));
    pair<int,int> fcoo = M[{ui,di,li,ri}];
    //cout << fcoo.first <<" " << fcoo.second << endl;
    pair<int,int> oocoord = {orgx-fcoo.first*gsize, orgy-fcoo.second*gsize};
    pair<int,int> answer = {oocoord.first+2*gsize, oocoord.second+2*gsize};
    cout << answer.first <<" " << answer.second << endl;
}

Compilation message (stderr)

aliens.cpp: In function 'int main()':
aliens.cpp:25:9: warning: unused variable 'maxn' [-Wunused-variable]
   25 |     int maxn=2000000000;
      |         ^~~~
aliens.cpp:153:9: warning: unused variable 'coordx' [-Wunused-variable]
  153 |     int coordx=0;
      |         ^~~~~~
aliens.cpp:154:9: warning: unused variable 'coordy' [-Wunused-variable]
  154 |     int coordy=0;
      |         ^~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10