QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#428080#6303. InversioncomeintocalmTL 0ms0kbC++201.5kb2024-06-01 17:20:162024-06-01 17:20:17

Judging History

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

  • [2024-06-01 17:20:17]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2024-06-01 17:20:16]
  • 提交

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();
}

详细

Test #1:

score: 0
Time Limit Exceeded

input:

3

output:


result: