Submission #1362605

#TimeUsernameProblemLanguageResultExecution timeMemory
1362605AvianshMineral deposits (BOI23_mineraldeposits)C++20
46 / 100
1 ms424 KiB
#include <bits/stdc++.h>

using namespace std;

mt19937 rng(1234);

signed main(){
    int b,k,w;
    cin >> b >> k >> w;
    cout << "? " << -b << " " << -b << endl;
    vector<int>bot(k);
    for(int i = 0;i<k;i++){
        cin >> bot[i];
    }

    cout << "? " << -b << " " << b << endl;
    vector<int>top(k);
    for(int i = 0;i<k;i++){
        cin >> top[i];
    }
    //find intersections
    set<array<int,2>>pts;
    for(int i : bot){
        for(int j : top){
            if(i+j>=2*b){
                //intersect
                int dist = (i+j-2*b);
                if(dist%2){
                    //bad intersection
                    continue;
                }
                //good intersection
                int y = b-j+dist/2;
                int x = -b+dist/2;
                pts.insert({x,y});
            }
        }
    }
    //for testing just check one by one
    //prune
    set<array<int,2>>pruned;

    for(array<int,2>a:pts){
        if(-b<=a[0]&&a[0]<=b&&-b<=a[1]&&a[1]<=b){
            pruned.insert(a);
        }
    }
    set<array<int,2>>ans;
    array<int,2>rigpt = {b,0};
    ans=pruned;
    set<array<int,2>>querd;
    while(ans.size()>k){
        vector<array<int,2>>curr;
        for(array<int,2>a:ans){
            curr.push_back(a);
        }
        array<int,2>pt = curr[rng()%(curr.size())];
        while(querd.find(pt)!=querd.end()){
            pt = curr[rng()%(curr.size())];
        }
        querd.insert(pt);
        cout << "? " << pt[0] << " " << pt[1] << endl;
        vector<int>rig(k);
        for(int i = 0;i<k;i++){
            cin >> rig[i];
        }
        set<array<int,2>>temp;
        for(array<int,2>a:ans){
            bool wor = 0;
            int dist = abs(pt[0]-a[0])+abs(pt[1]-a[1]);
            for(int i : rig){
                if(dist==i){
                    wor=1;
                }
            }
            if(wor){
                temp.insert(a);
            }
        }
        ans=temp;
    }
    //assert(ans.size()==k);
    cout << "! ";
    for(array<int,2>a:ans){
        cout << a[0] << " " << a[1] << " ";
    }
    cout << endl;
    return 0;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...