QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#332834#6303. InversionScanoWA 76ms19268kbC++201.8kb2024-02-19 16:10:202024-02-19 16:10:20

Judging History

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

  • [2024-02-19 16:10:20]
  • 评测
  • 测评结果:WA
  • 用时:76ms
  • 内存:19268kb
  • [2024-02-19 16:10:20]
  • 提交

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 = 2000;
int mp[nax][nax];



vector<int> arr;
int preguntas = 0;

int get(int l, int r){
  if(l == r) return 0;
  if(mp[l][r]!=-1) return mp[l][r];
  ++preguntas;
  cout << "? " << l + 1 << " " << r + 1 << el;
  int x;
  cin >> x;
  return mp[l][r] = 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 = rand()%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;

  memset(mp, -1, sizeof mp);
  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;

}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 19212kb

input:

3
0
1
0

output:

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

result:

ok OK, guesses=3

Test #2:

score: -100
Wrong Answer
time: 76ms
memory: 19268kb

input:

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

output:

? 1 575
? 2 575
? 1 574
? 2 574
? 3 575
? 3 574
? 4 575
? 4 574
? 5 575
? 5 574
? 6 575
? 6 574
? 7 575
? 7 574
? 8 575
? 8 574
? 9 575
? 9 574
? 10 575
? 10 574
? 11 575
? 11 574
? 12 575
? 12 574
? 13 575
? 13 574
? 14 575
? 14 574
? 15 575
? 15 574
? 16 575
? 16 574
? 17 575
? 17 574
? 18 575
? 1...

result:

wrong output format Unexpected end of file - int32 expected