제출 #1360880

#제출 시각아이디문제언어결과실행 시간메모리
1360880AvianshStaring Contest (BOI23_staringcontest)C++20
100 / 100
4 ms520 KiB
#include <bits/stdc++.h>

using namespace std;

map<array<int,2>,int>mem;

int query(int a, int b){
    if(a>b)
        swap(a,b);
    if(mem[{a,b}]!=0){
        return mem[{a,b}];
    }
    cout << "? " << a+1 << " " << b+1 << endl;
    cin >> mem[{a,b}];
    return mem[{a,b}];
}

signed main(){
    int n;
    cin >> n;
    vector<int>left(n);
    iota(left.begin(),left.end(),0);
    int ans[n];
    fill(ans,ans+n,-1);
    auto pick = [&] (){
        int r = rand()%(left.size());
        swap(left[r],left[left.size()-1]);
        r=left.back();
        left.pop_back();
        return r;
    };
    int a = pick();
    int b = pick();
    while(left.size()){
        int c = pick();
        if(query(a,b)==query(a,c)){
            ///a is minima so remove
            ans[a]=query(a,b);
            a=c;
        }
        else{
            if(query(a,b)<query(a,c)){
                //b is minima
                ans[b]=query(a,b);
                b=c;
            }
            else{
                //c is minima
                ans[c]=query(a,c);
            }
        }
    }
    ans[a]=ans[b]=query(a,b);
    cout << "! ";
    for(int i : ans){
        cout << i << " ";
    }
    cout << endl;
    return 0;
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…