QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#191546#7535. Limited Shuffle RestoringDays_of_Future_Past#WA 1ms4072kbC++144.0kb2023-09-30 01:06:062023-09-30 01:06:06

Judging History

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

  • [2023-09-30 01:06:06]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4072kb
  • [2023-09-30 01:06:06]
  • 提交

answer

#include <bits/stdc++.h>
#define SZ(c) ((int)(c).size())
#define ONLINE 1

using namespace std;

const int N = 3e4+10;
mt19937 gene(233);
typedef pair<int, int> pii;

int n;
int a[11];

void dfs(int i) {
  if (i == n) {
    for (int j = 1; j <= n; ++j)
      printf("%d ", a[j]);
    puts("");
    return;
  }
  dfs(i + 1);
  swap(a[i], a[i+1]);
  dfs(i + 1);
  swap(a[i], a[i+1]);
  if (i + 2 <= n) {
    swap(a[i], a[i+2]);
    dfs(i + 1);
    swap(a[i], a[i+2]);
  }
}

void build() {
  n = 5;
  for (int i = 1; i <= n; ++i)
    a[i] = i;
  dfs(1);
}

int query_cnt;
vector<int> groundtruth{0, 2, 3, 5, 1, 4};

bool query(int i, int j) {
  static char buf[111];
  assert(i != j);
  printf("? %d %d\n", i, j);
  fflush(stdout);

  if (ONLINE) {
    scanf("%s", buf);
    return buf[0] == '<';
  } else {
    query_cnt++;
    int ub = (5 * n) / 3 + 5;
    if (query_cnt > ub) {
      printf("boom %d\n", ub);
      assert(false);
    }
    return groundtruth[i] < groundtruth[j];
  }
}

map<pii, bool> mp;

bool cached_query(int i, int j) {
  if (mp.count(pii(i, j))) {
    return mp[pii(i, j)];
  } else {
    bool res = query(i, j);
    mp[pii(i, j)] = res;
    mp[pii(j, i)] = !res;
    return res;
  }
}

void answer(const vector<int> &xs) {
  printf("!");
  for (int i = 1; i <= n; ++i) {
    printf(" %d", xs[i]);
    if (!ONLINE)
      assert(groundtruth[i] == xs[i]);
  }
  printf("\n");
  fflush(stdout);
}

int argmax(const set<int> &cand) {
  int mx_i = -1;
  for (int x: cand) {
    if (mx_i == -1)
      mx_i = x;
    else if (cached_query(mx_i, x)) {
      mx_i = x;
    }
  }
  return mx_i;
}


void main2() {
  if (n == 1) {
    vector<int> ans(2);
    ans[1] = 1;
    answer(ans);
    return;
  }
  if (n == 2) {
    vector<int> ans(3);
    ans[1] = 1;
    ans[2] = 2;
    if (!query(1, 2))
      swap(ans[1], ans[2]);
    answer(ans);
    return;
  }
  vector<int> ans(n + 1);
  int A = n, B = n - 1;
  if (cached_query(A, B))
    swap(A, B);
  for (int i = n; i > 0; --i) {
    //printf("i %d A %d B %d\n", i, A, B);
    if (i == 2) {
      ans[A] = 2;
      ans[B] = 1;
      break;
    }
    int C = i - 2;
    if (gene() % 2 == 1)
      swap(A, B);
    if (gene() % 2 == 1)
      swap(B, C);
    if (gene() % 2 == 1)
      swap(A, C);
    if (cached_query(A, B)) { // A < B
      if (cached_query(B, C)) { // B < C
        ans[C] = i;
      } else { // A < B
        ans[B] = i;
        tie(A, B) = pii(A, C);
      }
    } else { // A > B
      if (cached_query(A, C)) { // A < C
        ans[C] = i;
      } else {
        ans[A] = i;
        tie(A, B) = pii(B, C);
      }
    }
  }
  answer(ans);
}

void main3() {
  if (n == 1) {
    vector<int> ans(2);
    ans[1] = 1;
    answer(ans);
    return;
  }
  if (n == 2) {
    vector<int> ans(3);
    ans[1] = 1;
    ans[2] = 2;
    if (!query(1, 2))
      swap(ans[1], ans[2]);
    answer(ans);
    return;
  }
  vector<int> ans(n + 1);
  int A = n, B = n - 1;
  if (cached_query(A, B))
    swap(A, B);
  for (int i = n; i > 0; --i) {
    //printf("i %d A %d B %d\n", i, A, B);
    if (i == 2) {
      ans[A] = 2;
      ans[B] = 1;
      break;
    }
    int C = i - 2;
    if (cached_query(A, C)) {
      ans[C] = i;
    } else {
      ans[A] = i;
      A = C;
      if (cached_query(A, B))
        swap(A, B);
    }
  }
  answer(ans);
}

int main() {
  //build();
  //n = 100;
  //groundtruth.resize(n + 1);
  //for (int i = 1; i <= n; ++i)
    //groundtruth[i] = i;
  //srand(time(NULL) ^ 0xc2251393);
  //for (int i = 1; i <= n; ++i) {
    //int j = min(i + rand() % 3, n);
    //int j = min(i + 1, n);
    //swap(groundtruth[i], groundtruth[j]);
  //}
  //printf("ans");
  //for (int i = 1; i <= n; ++i)
    //printf(" %d", groundtruth[i]);
  //printf("\n");
  int tc = 1;
  while (tc--) {
	  
  if (ONLINE) {
    scanf("%d", &n);
  } else {
    n = SZ(groundtruth) - 1;
  }
  if(n <= 15) 
    main3();
  else main2();
  }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

5
<
>
<
>
>
>
>

output:

? 5 4
? 4 3
? 3 5
? 5 2
? 2 3
? 2 1
? 1 3
! 2 3 1 5 4

result:

ok yeah, seems ok, spent 7 queries of 13

Test #2:

score: 0
Accepted
time: 1ms
memory: 3804kb

input:

1

output:

! 1

result:

ok yeah, seems ok, spent 0 queries of 6

Test #3:

score: 0
Accepted
time: 0ms
memory: 3776kb

input:

2
>

output:

? 1 2
! 2 1

result:

ok yeah, seems ok, spent 1 queries of 8

Test #4:

score: 0
Accepted
time: 0ms
memory: 3772kb

input:

3
<
>
>

output:

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

result:

ok yeah, seems ok, spent 3 queries of 10

Test #5:

score: 0
Accepted
time: 0ms
memory: 3772kb

input:

4
<
>
>
>
>

output:

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

result:

ok yeah, seems ok, spent 5 queries of 11

Test #6:

score: 0
Accepted
time: 1ms
memory: 3800kb

input:

5
<
>
>
>
>
>
>

output:

? 5 4
? 4 3
? 3 5
? 3 2
? 2 5
? 2 1
? 1 5
! 2 3 4 5 1

result:

ok yeah, seems ok, spent 7 queries of 13

Test #7:

score: 0
Accepted
time: 1ms
memory: 3772kb

input:

6
<
>
>
>
>
>
>
>
>

output:

? 6 5
? 5 4
? 4 6
? 4 3
? 3 6
? 3 2
? 2 6
? 2 1
? 1 6
! 2 3 4 5 6 1

result:

ok yeah, seems ok, spent 9 queries of 15

Test #8:

score: 0
Accepted
time: 1ms
memory: 3780kb

input:

7
<
>
>
>
>
>
>
>
>
>
>

output:

? 7 6
? 6 5
? 5 7
? 5 4
? 4 7
? 4 3
? 3 7
? 3 2
? 2 7
? 2 1
? 1 7
! 2 3 4 5 6 7 1

result:

ok yeah, seems ok, spent 11 queries of 16

Test #9:

score: 0
Accepted
time: 1ms
memory: 4072kb

input:

8
<
>
>
>
>
>
>
>
>
>
>
>
>

output:

? 8 7
? 7 6
? 6 8
? 6 5
? 5 8
? 5 4
? 4 8
? 4 3
? 3 8
? 3 2
? 2 8
? 2 1
? 1 8
! 2 3 4 5 6 7 8 1

result:

ok yeah, seems ok, spent 13 queries of 18

Test #10:

score: 0
Accepted
time: 1ms
memory: 3872kb

input:

9
<
>
>
>
>
>
>
>
>
>
>
>
>
>
>

output:

? 9 8
? 8 7
? 7 9
? 7 6
? 6 9
? 6 5
? 5 9
? 5 4
? 4 9
? 4 3
? 3 9
? 3 2
? 2 9
? 2 1
? 1 9
! 2 3 4 5 6 7 8 9 1

result:

ok yeah, seems ok, spent 15 queries of 20

Test #11:

score: 0
Accepted
time: 1ms
memory: 3804kb

input:

10
<
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>

output:

? 10 9
? 9 8
? 8 10
? 8 7
? 7 10
? 7 6
? 6 10
? 6 5
? 5 10
? 5 4
? 4 10
? 4 3
? 3 10
? 3 2
? 2 10
? 2 1
? 1 10
! 2 3 4 5 6 7 8 9 10 1

result:

ok yeah, seems ok, spent 17 queries of 21

Test #12:

score: 0
Accepted
time: 1ms
memory: 4028kb

input:

11
<
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>

output:

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

result:

ok yeah, seems ok, spent 19 queries of 23

Test #13:

score: 0
Accepted
time: 1ms
memory: 3860kb

input:

12
<
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>

output:

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

result:

ok yeah, seems ok, spent 21 queries of 25

Test #14:

score: 0
Accepted
time: 0ms
memory: 4072kb

input:

13
<
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>

output:

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

result:

ok yeah, seems ok, spent 23 queries of 26

Test #15:

score: 0
Accepted
time: 1ms
memory: 3776kb

input:

14
<
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>

output:

? 14 13
? 13 12
? 12 14
? 12 11
? 11 14
? 11 10
? 10 14
? 10 9
? 9 14
? 9 8
? 8 14
? 8 7
? 7 14
? 7 6
? 6 14
? 6 5
? 5 14
? 5 4
? 4 14
? 4 3
? 3 14
? 3 2
? 2 14
? 2 1
? 1 14
! 2 3 4 5 6 7 8 9 10 11 12 13 14 1

result:

ok yeah, seems ok, spent 25 queries of 28

Test #16:

score: 0
Accepted
time: 1ms
memory: 4036kb

input:

15
<
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>

output:

? 15 14
? 14 13
? 13 15
? 13 12
? 12 15
? 12 11
? 11 15
? 11 10
? 10 15
? 10 9
? 9 15
? 9 8
? 8 15
? 8 7
? 7 15
? 7 6
? 6 15
? 6 5
? 5 15
? 5 4
? 4 15
? 4 3
? 3 15
? 3 2
? 2 15
? 2 1
? 1 15
! 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1

result:

ok yeah, seems ok, spent 27 queries of 30

Test #17:

score: -100
Wrong Answer
time: 1ms
memory: 3780kb

input:

16
<
>
>
>
<
>
<
>
<
>
>
>
>
>
<
>
>
>
<
>
>
>
<
>
<
>
<
>

output:

? 16 15
? 15 14
? 13 14
? 13 16
? 14 12
? 12 16
? 16 11
? 11 14
? 16 10
? 10 14
? 9 14
? 9 16
? 8 16
? 8 14
? 14 7
? 7 16
? 14 16
? 14 6
? 6 5
? 5 16
? 4 16
? 4 6
? 16 6
? 6 3
? 16 2
? 2 3
? 3 1
? 1 16
! 3 4 2 6 7 5 9 10 11 12 13 14 15 8 16 1

result:

wrong answer this is not the only answer, for example, we could have guessed [3, 4, 1, 6, 7, 5, 9, 10, 11, 12, 13, 14, 15, 8, 16, 2]