QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#191548#7535. Limited Shuffle RestoringDays_of_Future_Past#WA 1ms4100kbC++144.0kb2023-09-30 01:06:452023-09-30 01:06:45

Judging History

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

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

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 <= 19) 
    main3();
  else main2();
  }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 4088kb

input:

1

output:

! 1

result:

ok yeah, seems ok, spent 0 queries of 6

Test #3:

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

input:

2
>

output:

? 1 2
! 2 1

result:

ok yeah, seems ok, spent 1 queries of 8

Test #4:

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

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: 1ms
memory: 3760kb

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: 3860kb

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: 3832kb

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: 3800kb

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: 3880kb

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: 3804kb

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: 4100kb

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: 3796kb

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: 3808kb

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: 1ms
memory: 3748kb

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: 3792kb

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: 3804kb

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: 0
Accepted
time: 1ms
memory: 3824kb

input:

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

output:

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

result:

ok yeah, seems ok, spent 29 queries of 31

Test #18:

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

input:

17
<
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>

output:

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

result:

ok yeah, seems ok, spent 31 queries of 33

Test #19:

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

input:

18
<
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>

output:

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

result:

ok yeah, seems ok, spent 33 queries of 35

Test #20:

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

input:

19
<
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>

output:

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

result:

ok yeah, seems ok, spent 35 queries of 36

Test #21:

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

input:

20
<
>
>
>
<
>
<
>
<
>
>
>
>
>
<
>
>
>
<
>
>
>
<
>
<
>
<
>
>
>
<
>
<
>
<
>

output:

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

result:

wrong answer this is not the only answer, for example, we could have guessed [3, 4, 5, 6, 7, 8, 2, 10, 11, ... 15, 16, 17, 18, 19, 12, 20, 1]