QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#109448#5206. Hot and Coldgigabuffoon#TL 0ms0kbC++209.5kb2023-05-29 02:14:302023-05-29 02:14:33

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-29 02:14:33]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2023-05-29 02:14:30]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define all(x) begin(x), end(x)
#define sz(x) int(size(x))
#define rep(a, b, c) for (int a = (b); a < (c); a++)
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;

map<string, int> ids;
const int MAX_X = 1'000'000;

int CLOSER = -1;
int FURTHER = -1;
int SAME = -1;

ll ansX, ansY;
ll lastD = -1;

int queries = 0;

// int query(ll x, ll y) {
//     cout << x << " " << y << endl;
//     queries++;

//     if (tie(x, y) == tie(ansX, ansY)) {
//         cout << "found in " << queries << "!" << endl;
//         exit(0);
//     }

//     ll dx = x - ansX, dy = y - ansY;
//     ll dist = dx*dx + dy*dy;

//     int ret;
//     if (lastD == -1) ret = 0;
//     else if (lastD < dist) ret = 1;
//     else if (lastD > dist) ret = 2;
//     else ret = 3;

//     lastD = dist;
//     cout << "said " << ret << "\n";
    
//     if (CLOSER != -1 && FURTHER != -1 && SAME == -1 && ret != CLOSER && ret != FURTHER) {
//         cout << "Found same!" << endl;
//         SAME = ret;
//     }

//     return ret;
// }

int query(int x, int y) {
    cout << x << " " << y << endl;
    string ret;
    cin >> ret;

    if (ret.back() == '!') {
        exit(0);
    }

    int rval;

    if (ids.count(ret)) rval = ids[ret];
    else rval = ids[ret] = sz(ids);

    if (CLOSER != -1 && FURTHER != -1 && SAME == -1 && rval != CLOSER && rval != FURTHER)
        SAME = rval;

    return rval;
}

void solve() {
    query(0, 0);
    int v1 = query(1, 0);
    query(0, 0);
    int v2 = query(0, 1);

    int loX = 0, hiX = MAX_X;
    int loY = 0, hiY = MAX_X;
    int lastX = 0;
    int lastY = 0;

    if (v1 == v2) {
        CLOSER = v1;
        FURTHER = query(0, 0);
    }
    else {
        query(MAX_X, 0);
        query(0, MAX_X);
        query(MAX_X, MAX_X);
        int v3 = query(MAX_X, MAX_X-1);
        CLOSER = v3;
        FURTHER = (v3 == v1 ? v2 : v1);

        // SAVE QUERIES 
        query(0, 0);
        if (query(1, 0) == CLOSER) loY = hiY = 0;
        else loX = hiX = 0;
    }

    // cout << "CLOSER: " << CLOSER << "\n";
    // cout << "FURTHER: " << FURTHER << "\n";
    // cout << "SAME: " << SAME << "\n";
    // cout.flush();
    ll wantX = loX, wantY = loY;

    bool doY = 0;

    while (loX < hiX || loY < hiY) {
        if (doY || loX == hiX) {
            int next = clamp(loY + hiY - lastY, 0, MAX_X);
            int ret = query(lastX, next);

            // cout << "loY " << loY << " hiY " << hiY << " lastY " << lastY << " next " << next << "\n";

            int cutLo = (lastY + next) / 2;
            int cutHi = (lastY + next + 1) / 2;

            if (ret == SAME) {
                assert((lastY + next) % 2 == 0);
                loY = hiY = (lastY + next) / 2;
            }
            else if (lastY < next) {
                if (ret == CLOSER) loY = max(loY, cutHi);
                else hiY = min(hiY, cutLo);
            }
            else { // next < last
                if (ret == CLOSER) hiY = min(hiY, cutLo);
                else loY = max(loY, cutHi);
            }

            if (ret == FURTHER) {
                if (lastY < next)
                    wantY = loY;
                else
                    wantY = hiY;

                query(wantX, wantY);
                doY = 0;
                lastX = wantX;
                lastY = wantY;
            }
            else {
                lastY = next;
            }

        }    
        else { // do X

            int next = clamp(loX + hiX - lastX, 0, MAX_X);
            int ret = query(next, lastY);

            // cout << "loX " << loX << " hiX " << hiX << " lastX " << lastX << " next " << next << "\n";

            int cutLo = (lastX + next) / 2;
            int cutHi = (lastX + next + 1) / 2;

            if (ret == SAME) {
                assert((lastX + next) % 2 == 0);
                loX = hiX = (lastX + next) / 2;
            }
            else if (lastX < next) {
                if (ret == CLOSER) loX = max(loX, cutHi);
                else hiX = min(hiX, cutLo);
            }
            else { // next < last
                if (ret == CLOSER) hiX = min(hiX, cutLo);
                else loX = max(loX, cutHi);
            }

            if (ret == FURTHER) {
                if (loY < hiY) {
                    doY = 1;
                    lastX = next;
                
                    if (lastX < next)
                        wantX = loX;
                    else
                        wantX = hiX;
                }
                else {              
                    if (lastX < next)
                        wantX = loX;
                    else
                        wantX = hiX;

                    query(wantX, loY);
                    lastX = wantX;
                }
            }
            else {
                wantX = next;
                lastX = next;
            }
        }   
    }

    // cout << "GOT " << loX << " " << loY << endl;
    query(loX, loY);

    // cout << "bruv" << endl;
}

int main() {
    cin.tie(0)->sync_with_stdio(false);
    cin.exceptions(cin.failbit);
 
    cin >> ansX >> ansY;

    solve(); 
    return 0;
}


/*
20 20
0 0
said 0
1 0
said 2
0 0
said 1
0 1
said 2
0 0
said 1
CLOSER: 2
FURTHER: 1
SAME: -1
1000000 0
said 1
loX 0 hiX 1000000 lastX 0 next 1000000
1000000 1000000
said 1
loY 0 hiY 1000000 lastY 0 next 1000000
500000 0
said 2
0 0
said 2
loX 0 hiX 500000 lastX 500000 next 0
250000 0
said 1
loX 0 hiX 250000 lastX 0 next 250000
250000 500000
said 1
loY 0 hiY 500000 lastY 0 next 500000
125000 0
said 2
0 0
said 2
loX 0 hiX 125000 lastX 125000 next 0
62500 0
said 1
loX 0 hiX 62500 lastX 0 next 62500
62500 250000
said 1
loY 0 hiY 250000 lastY 0 next 250000
31250 0
said 2
0 0
said 2
loX 0 hiX 31250 lastX 31250 next 0
15625 0
said 1
loX 0 hiX 15625 lastX 0 next 15625
15625 125000
said 1
loY 0 hiY 125000 lastY 0 next 125000
7812 0
said 2
0 0
said 2
loX 0 hiX 7812 lastX 7812 next 0
3906 0
said 1
loX 0 hiX 3906 lastX 0 next 3906
3906 62500
said 1
loY 0 hiY 62500 lastY 0 next 62500
1953 0
said 2
0 0
said 2
loX 0 hiX 1953 lastX 1953 next 0
976 0
said 1
loX 0 hiX 976 lastX 0 next 976
976 31250
said 1
loY 0 hiY 31250 lastY 0 next 31250
488 0
said 2
0 0
said 2
loX 0 hiX 488 lastX 488 next 0
244 0
said 1
loX 0 hiX 244 lastX 0 next 244
244 15625
said 1
loY 0 hiY 15625 lastY 0 next 15625
122 0
said 2
0 0
said 2
loX 0 hiX 122 lastX 122 next 0
61 0
said 1
loX 0 hiX 61 lastX 0 next 61
61 7812
said 1
loY 0 hiY 7812 lastY 0 next 7812
30 0
said 2
0 0
said 1
loX 0 hiX 30 lastX 30 next 0
0 3906
said 1
loY 0 hiY 3906 lastY 0 next 3906
30 0
said 2
15 0
said 2
loX 15 hiX 30 lastX 30 next 15
22 0
said 2
loX 15 hiX 22 lastX 15 next 22
19 0
said 2
loX 19 hiX 22 lastX 22 next 19
20 0
said 2
loX 19 hiX 20 lastX 19 next 20
20 1953
said 1
loY 0 hiY 1953 lastY 0 next 1953
20 0
said 2
20 976
said 1
loY 0 hiY 976 lastY 0 next 976
20 0
said 2
20 488
said 1
loY 0 hiY 488 lastY 0 next 488
20 0
said 2
20 244
said 1
loY 0 hiY 244 lastY 0 next 244
20 0
said 2
20 122
said 1
loY 0 hiY 122 lastY 0 next 122
20 0
said 2
20 61
said 1
loY 0 hiY 61 lastY 0 next 61
20 0
said 2
20 30
said 2
loY 0 hiY 30 lastY 0 next 30
20 15
said 2
loY 15 hiY 30 lastY 30 next 15
20 22
said 2
loY 15 hiY 22 lastY 15 next 22
20 19
said 2
loY 19 hiY 22 lastY 22 next 19
20 20
found in 60!
team@phuket:~/2023-05-28$ ./a.out
0 100
0 0
said 0
1 0
said 1
0 0
said 2
0 1
said 2
1000000 0
said 1
0 1000000
said 2
1000000 1000000
said 1
1000000 999999
said 2
0 0
said 2
1 0
said 1
CLOSER: 2
FURTHER: 1
SAME: -1
0 1000000
said 1
loY 0 hiY 1000000 lastY 0 next 1000000
-8085618620831142656 0
said 1
739470592 500000
said 2
loY 0 hiY 500000 lastY 0 next 500000
739470592 250000
said 2
loY 250000 hiY 500000 lastY 500000 next 250000
739470592 375000
said 1
loY 250000 hiY 375000 lastY 250000 next 375000
-8085618620831142656 250000
said 1
739470592 312500
said 2
loY 250000 hiY 312500 lastY 250000 next 312500
739470592 281250
said 2
loY 281250 hiY 312500 lastY 312500 next 281250
739470592 296875
said 1
loY 281250 hiY 296875 lastY 281250 next 296875
-8085618620831142656 281250
said 1
739470592 289062
said 2
loY 281250 hiY 289062 lastY 281250 next 289062
739470592 285156
said 2
loY 285156 hiY 289062 lastY 289062 next 285156
739470592 287109
said 1
loY 285156 hiY 287109 lastY 285156 next 287109
-8085618620831142656 285156
said 1
739470592 286132
said 2
loY 285156 hiY 286132 lastY 285156 next 286132
739470592 285644
said 2
loY 285644 hiY 286132 lastY 286132 next 285644
739470592 285888
said 1
loY 285644 hiY 285888 lastY 285644 next 285888
-8085618620831142656 285644
said 1
739470592 285766
said 2
loY 285644 hiY 285766 lastY 285644 next 285766
739470592 285705
said 2
loY 285705 hiY 285766 lastY 285766 next 285705
739470592 285735
said 1
loY 285705 hiY 285735 lastY 285705 next 285735
-8085618620831142656 285705
said 1
739470592 285720
said 2
loY 285705 hiY 285720 lastY 285705 next 285720
739470592 285713
said 2
loY 285713 hiY 285720 lastY 285720 next 285713
739470592 285716
said 1
loY 285713 hiY 285716 lastY 285713 next 285716
-8085618620831142656 285713
said 1
739470592 285714
said 2
loY 285713 hiY 285714 lastY 285713 next 285714
GOT 0 285714
0 285714
said 2
bruv
*/

详细

Test #1:

score: 0
Time Limit Exceeded

input:


output:


result: