QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#332816#6303. InversionScanoRE 1ms3600kbC++201.8kb2024-02-19 16:07:082024-02-19 16:07:09

Judging History

你现在查看的是最新测评结果

  • [2024-02-19 16:07:09]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:3600kb
  • [2024-02-19 16:07:08]
  • 提交

answer

#include <bits/stdc++.h>

#define sz(v) v.size()
#define forn(i,n) for(int i = 0; i < n; ++i)
#define fi first
#define se second
#define el endl
#define all(v) v.begin(),v.end()
#define pb push_back
#define d(x) cout << #x << " : " << x << el

using namespace std;

typedef pair<int,int> ii;
typedef long long ll;
typedef tuple<ll,int,int> iii;

int dr[] = {1,0,-1,0};
int dc[] = {0,1,0,-1};

const int nax = 1e5 + 20;

vector<int> arr;
int preguntas = 0;

int get(int l, int r){
  if(l == r) return 0;
  ++preguntas;
  assert(preguntas <= 4e4);
  cout << "? " << l + 1 << " " << r + 1 << el;
  int x;
  cin >> x;
  return x;
}

int ask(int l, int r){
  if(l+1==r){
    return get(l, r);
  }
  int vlr = get(l, r);
  int vl_r = get(l+1,r);
  int vlr_ = get(l, r-1);
  int vl_r_ = get(l+1, r-1);
  return ((vlr - vl_r - vlr_ + vl_r_)%2 + 2)%2;
}


void solve(vector<int> &pos, int start = 0){
  int r = random()%sz(pos);
  vector<int> ls, rs;
  int cnt = 0;
  forn(i,sz(pos)){
    if(i == r) continue;
    int val = 0;
    if(i < r){
      val = ask(pos[i], pos[r]);
      if(val == 0){
        ++cnt;
        ls.pb(pos[i]);
      }else{
        rs.pb(pos[i]);
      }
    }else{
      val = ask(pos[r], pos[i]);
      if(val == 1){
        ls.pb(pos[i]);
        ++cnt;
      }else{
        rs.pb(pos[i]);
      }
    }
  }
  arr[pos[r]] = start + 1 + cnt;
  if(sz(ls)) solve(ls, start);
  if(sz(rs)) solve(rs, arr[pos[r]]);
}


int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
  cout << setprecision(20)<< fixed;

  int n;
  cin >> n;
  arr.resize(n);
  vector<int> pos;
  forn(i,n){
    pos.pb(i);
  }
  solve(pos);
  cout << "! ";
  forn(i,n){
    cout << arr[i] << " ";
  }
  cout << el;

}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3600kb

input:

3
0
1
0
1
0

output:

? 1 2
? 2 3
? 1 3
? 2 3
? 1 2
! 2 3 1 

result:

ok OK, guesses=5

Test #2:

score: -100
Runtime Error

input:

1993
0
1
1
1
1
0
1
1
0
1
1
1
1
0
1
1
0
1
1
0
1
1
0
1
1
1
1
1
1
0
1
1
0
0
1
0
0
0
0
0
0
1
0
0
1
1
0
1
1
0
1
1
0
1
1
0
1
1
0
1
1
1
1
0
1
1
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
1
1
1
1
0
1
0
0
0
0
0
0
0
0
1
0
0
1
0
0
0
0
1
0
1
1
0
1
0
0
1
0
1
1
0
1
1
0
0
1
0
0
0
0
0
0
0
0
1
0
1
1
0
1
0
0
0
0
1
0
1
1
1
1
0
1
0...

output:

? 1 575
? 2 575
? 1 574
? 2 574
? 2 575
? 3 575
? 2 574
? 3 574
? 3 575
? 4 575
? 3 574
? 4 574
? 4 575
? 5 575
? 4 574
? 5 574
? 5 575
? 6 575
? 5 574
? 6 574
? 6 575
? 7 575
? 6 574
? 7 574
? 7 575
? 8 575
? 7 574
? 8 574
? 8 575
? 9 575
? 8 574
? 9 574
? 9 575
? 10 575
? 9 574
? 10 574
? 10 575
?...

result: