Submission #1363698

#TimeUsernameProblemLanguageResultExecution timeMemory
1363698SmuggingSpunStaring Contest (BOI23_staringcontest)C++20
95 / 100
6 ms9664 KiB
#include<bits/stdc++.h>
using namespace std;
const int lim = 1505;
template<class T>void maximize(T& a, T b){
  if(a < b){
    a = b;
  }
}
int n, ans[lim], f[lim][lim];
int ask(int i, int j){
  if(i > j){
    swap(i, j);
  }
  if(f[i][j] == -1){
    cout << "? " << i << " " << j << endl;
    cin >> f[i][j];
  }
  return f[i][j];
}
namespace sub1{
  void solve(){
    for(int i = 1; i <= n; i++){
      for(int j = 1; j <= n; j++){
        if(i != j){
          maximize(ans[i], ask(i, j));
        }
      }
    }
    cout << "! ";
    for(int i = 1; i <= n; i++){
      cout << ans[i] << " ";
    }
  }
}
namespace sub23{
  const int LIM = 86405;
  int pos[LIM];
  mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
  void solve(){
    vector<int>p(n);
    iota(p.begin(), p.end(), 1);
    shuffle(p.begin(), p.end(), rng);
    for(int i = 0; i < n; i++){
      if(ans[p[i]] != -1){
        continue;
      }
      memset(pos, -1, sizeof(pos));
      int max_min = 1;
      for(int j = i + 1; j < n; j++){
        if(ans[p[j]] != -1){
          continue;
        }
        int x = ask(p[i], p[j]);
        if(pos[x] != -1){
          ans[p[pos[ans[p[i]] = x]]] = max_min = -1;
          i = pos[x] - 1;
          break;
        }
        else{
          maximize(max_min, ans[p[pos[x] = j]] = x);
        }
      }
      if(max_min != -1){
        ans[p[i]] = max_min;
      }
    } 
    cout << "! ";
    for(int i = 1; i <= n; i++){
      cout << max(ans[i], 1) << " ";
    }
  }
}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  memset(f, -1, sizeof(f));
  memset(ans, -1, sizeof(ans));
  cin >> n;
  if(n <= 50){
    sub1::solve();
  }
  else{
    sub23::solve();
  }
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...