Submission #1362776

#TimeUsernameProblemLanguageResultExecution timeMemory
1362776AvianshMineral deposits (BOI23_mineraldeposits)C++20
0 / 100
0 ms352 KiB
#include <bits/stdc++.h>

using namespace std;

const int mxb = 1e8;

mt19937 rng(1234);
int b,k,w;

vector<array<int,2>> div1(){
    cout << "? " << -b << " " << -b << " " << -b << " " << b<< endl;
    vector<int>bot(k*2);
    for(int i = 0;i<k*2;i++){
        cin >> bot[i];
    }
    vector<int>top(k*2);
    for(int i = 0;i<k*2;i++){
        top[i]=bot[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});
            }
        }
    }
    //prune
    vector<array<int,2>>pruned;

    for(array<int,2>a:pts){
        if(-b<=a[0]&&a[0]<=b&&-b<=a[1]&&a[1]<=b){
            pruned.push_back(a);
        }
    }
    return pruned;
}

signed main(){
    cin >> b >> k >> w;
    vector<array<int,2>>cands = div1();
    int n = cands.size();
    array<int,2> probes[n];
    set<int>crit;
    auto pick = [&] (){
        int x = rng();
        int y = rng();
        x%=mxb;
        y%=mxb;
        if(rng()%2)
            x=-x;
        if(rng()%2)
            y=-y;
        return (array<int,2>){x,y};
    };
    for(int i = 0;i<n;i++){
        array<int,2>curr = pick();
        while(1){
            bool wor = 1;
            for(array<int,2>a:cands){
                int dist = abs(curr[0]-a[0])+abs(curr[1]-a[1]);
                if(crit.find(dist)!=crit.end()){
                    wor=0;
                    break;
                }
            }
            if(wor)
                break;
            curr=pick();
        }
        //found
        int dist = abs(curr[0]-cands[i][0])+abs(curr[1]-cands[i][1]);
        crit.insert(dist);
        probes[i]=curr;
    }
    cout << "? ";
    for(array<int,2>a:probes){
        cout << a[0] << " " << a[1] << " ";
    }
    cout << endl;
    map<int,int>freq;
    for(int i = 0;i<n*k;i++){
        int c;
        cin >> c;
        freq[c]++;
    }
    set<array<int,2>>ans;
    for(int i = 0;i<n;i++){
        int curd = abs(probes[i][0]-cands[i][0])+abs(probes[i][1]-cands[i][1]);
        if(freq[curd]){
            //this is a real pt
            ans.insert(cands[i]);
            for(array<int,2>a:probes){
                int dist = abs(a[0]-cands[i][0])+abs(a[1]-cands[i][1]);
                freq[dist]--;
            }
        }
    }
    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...