제출 #1363700

#제출 시각아이디문제언어결과실행 시간메모리
1363700SmuggingSpunStaring Contest (BOI23_staringcontest)C++20
100 / 100
6 ms9660 KiB
#include<bits/stdc++.h>
using namespace std;
const int lim = 1505;
const int LIM = 86405;
template<class T>void maximize(T& a, T b){
  if(a < b){
    a = b;
  }
}
int n, ans[lim], pos[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];
}
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
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;
  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) << " ";
  }
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…