QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#428253#6303. InversioncomeintocalmWA 0ms5964kbC++201.6kb2024-06-01 18:06:132024-06-01 18:06:16

Judging History

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

  • [2024-06-01 18:06:16]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:5964kb
  • [2024-06-01 18:06:13]
  • 提交

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 = 1; i < mid; i++) {
    if(pos[i] > pos[mid]) cnt++;
  }
  //cout << "MID" << mid << "X" << x << "cnt" << cnt << "\n";
  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;
      //cout << "l:" << l << " r:" << r << "\n";
      if(check(mid, i)) tar = mid, r = mid - 1;
      else l = mid + 1;
    }
    if(l == r) {
      if(!check(tar, 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();
}

詳細信息

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 5964kb

input:

3
0
1

output:

? 1 2
? 2 3
! 3 2 1 

result:

wrong answer Wa.