QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#428082#6303. InversioncomeintocalmWA 70ms22276kbC++201.5kb2024-06-01 17:20:352024-06-01 17:20:36

Judging History

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

  • [2024-06-01 17:20:36]
  • 评测
  • 测评结果:WA
  • 用时:70ms
  • 内存:22276kb
  • [2024-06-01 17:20:35]
  • 提交

answer

#include<bits/stdc++.h>

using namespace std;

#define mp make_pair

const int N = 2e3+7;
int Q[N][N];
bool vis[N][N];

int query(int l, int r) {
  if(l == r) return 0;
  if(vis[l][r]) return Q[l][r];
  printf("? %d %d\n", l, r);
  cout.flush();
  int x;
  scanf("%d", &x);
  vis[l][r] = 1;
  Q[l][r] = x;
  return x;
}

int pos[N], tmp[N], n;

/// pos[mid]  the position of number ranked mid

void mov(int l, int i) {
  for(int x = 1; x < l; x++) 
    tmp[x] = pos[x];
  for(int x = l; x < i; x++)
    tmp[x + 1] = pos[x];
  tmp[l] = i;
  for(int x = 1; x <= i; x++)
    pos[x] = tmp[x];
}

int ask(int mid, int x) {
  int cnt = 0;
  for(int i = mid + 1; i < x; i++) {
    if(pos[i] < pos[mid]) cnt++;
  }
  return cnt & 1;
}


int check(int mid, int x) {
  int val = query(pos[mid], x) ^ query(pos[mid] + 1, x) ^ ask(mid, x);
  return val & 1;
}

void solve() {
  pos[1] = 1;
  for(int i = 2; i <= n; i++) {
    int l = 1, r = i - 1, tar = l;
    while(l < r) {
      int mid = (l + r) / 2;
      if(check(mid, i)) tar = mid, r = mid;
      else l = mid + 1;
    }
    if(l == r) {
      if(!check(r, i)) {
        pos[i] = i;
      } else mov(tar, i);
    } else mov(tar, i); 
  }

  for(int i = 1; i <= n; i++) tmp[pos[i]] = i;
  printf("! ");
  for(int i = 1; i <= n; i++) printf("%d ", tmp[i]);
  printf("\n");
}
int main() {
  scanf("%d", &n);
  if(n == 1) {
    printf("1\n");
    return 0;
  }
  solve();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3
0
0
1

output:

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

result:

ok OK, guesses=3

Test #2:

score: -100
Wrong Answer
time: 70ms
memory: 22276kb

input:

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

output:

? 1 2
? 1 3
? 2 3
? 2 4
? 3 4
? 2 5
? 3 5
? 1 5
? 2 6
? 3 6
? 4 6
? 5 6
? 2 7
? 3 7
? 1 7
? 5 7
? 6 7
? 2 8
? 3 8
? 5 8
? 6 8
? 7 8
? 1 9
? 2 9
? 8 9
? 7 9
? 1 10
? 2 10
? 3 10
? 4 10
? 5 10
? 6 10
? 7 10
? 1 11
? 2 11
? 4 11
? 5 11
? 3 11
? 2 12
? 3 12
? 4 12
? 5 12
? 6 12
? 7 12
? 10 12
? 11 12
? ...

result:

wrong answer Wa.