Submission #1338182

#TimeUsernameProblemLanguageResultExecution timeMemory
1338182MinbaevStaring Contest (BOI23_staringcontest)C++20
100 / 100
5 ms516 KiB
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

template <class T> using ste = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define rand(a, b)   uniform_int_distribution<int>(a, b)(rng) 
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

using ll = long long;

void solve() {
    
    int n;
    cin >> n;
    
    ste<int>st;
    for(int i = 1;i<=n;i++){
		st.insert(i);
	}
	
    vector<int>ind(n + 1);
    int cnt = 0;
    while(!st.empty()){
		int i = rand(0, (int)st.size() - 1);
		ind[++cnt] = *st.find_by_order(i);
		st.erase(st.find_by_order(i));
	}
    
    vector<int>res(n + 1);
	int a = ind[1], b = ind[2], x;
    
    cout << "? " << a << " " << b << endl;
    cin >> x;
    
    for(int i = 3;i<=n;i++){
		cout << "? " << b << " " << ind[i] << endl;
		int val; cin >> val;
		if(val == x){
			res[b] = x;
			b = ind[i];
			cout << "? " << a << " " << b << endl;
			cin >> x;
			continue;
		}
		if(val > x){
			res[a] = x;
			a = b;
			b = ind[i];
			x = val;
			continue;
		}
		if(val < x){
			res[ind[i]] = val;
			continue;
		}
	}
	
	res[a] = x;
	res[b] = x;
	
	cout << "! ";
	for(int i = 1;i<=n;i++){
		cout << res[i] << " ";
	}
	cout << endl;
    
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    int tt = 1;
    while (tt--) solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...