Submission #1362593

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

using namespace std;

mt19937 rng(1234);

const int mxb = 1e8;
int b,k,w;

set<array<int,2>> prune(set<array<int,2>>pts){
    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);
        }
    }
    return pruned;
}

set<array<int,2>>div1(){
    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});
            }
        }
    }
    //prune
    return prune(pts);
}

set<array<int,2>>div2(){
    cout << "? " << -b << " " << 0 << endl;
    vector<int>lef(k);
    for(int i = 0;i<k;i++){
        cin >> lef[i];
    }
    cout << "? " << b << " " << 0 << endl;
    vector<int>rig(k);
    for(int i = 0;i<k;i++){
        cin >> rig[i];
    }
    set<array<int,2>>pts;
    for(int i : lef){
        for(int j : rig){
            if(i+j>=2*b){
                //intersect
                int dist = (i+j-2*b);
                if(dist%2){
                    //bad intersection
                    continue;
                }
                //good intersection
                int x = i-b-dist/2;
                int y = dist/2;
                pts.insert({x,y});
                y=-y;
                pts.insert({x,y});
            }
        }
    }
    return prune(pts);
}

signed main(){
    cin >> b >> k >> w;

    set<array<int,2>>s1 = div1();
    set<array<int,2>>s2 = div2();

    set<array<int,2>>ans;
    for(array<int,2>a:s1){
        if(s2.find(a)==s2.end())
            continue;
        ans.insert(a);
    }

    //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...