QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#191539#7535. Limited Shuffle RestoringDays_of_Future_Past#WA 3ms4168kbC++143.4kb2023-09-30 01:01:082023-09-30 01:01:08

Judging History

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

  • [2023-09-30 01:01:08]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:4168kb
  • [2023-09-30 01:01:08]
  • 提交

answer

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

using namespace std;

const int N = 3e4+10;

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 (ONLINE) {
    scanf("%d", &n);
  } else {
    n = SZ(groundtruth) - 1;
  }
  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) {
      if (cached_query(A, B))
        swap(A, B);
      ans[A] = 2;
      ans[B] = 1;
      break;
    }
    int C = i - 2;
    int r1 = rand() % 3;
    if (r1 == 1) swap(A, B);
    else if (r1 == 2) swap(A, C);
    int r2 = rand() % 2;
    if (r2 == 1) swap(B, 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);
}

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 + 1, n);
    swap(groundtruth[i], groundtruth[j]);
  }
  //groundtruth = {0, 2, 3, 1, 5, 4};
  //printf("ans");
  //for (int i = 1; i <= n; ++i)
    //printf(" %d", groundtruth[i]);
  //printf("\n");
  int tc = 1;
  while (tc--) {
    main2();
  }
  if (!ONLINE) printf("total query %d\n", query_cnt);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

5
<
>
>
>
<
>
<

output:

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

result:

ok yeah, seems ok, spent 7 queries of 13

Test #2:

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

input:

1

output:

! 1

result:

ok yeah, seems ok, spent 0 queries of 6

Test #3:

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

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

input:

3
<
>
<

output:

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

result:

ok yeah, seems ok, spent 3 queries of 10

Test #5:

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

input:

4
<
>
<
>
<

output:

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

result:

ok yeah, seems ok, spent 5 queries of 11

Test #6:

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

input:

5
<
>
<
>
<
>
<

output:

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

result:

ok yeah, seems ok, spent 7 queries of 13

Test #7:

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

input:

6
<
>
<
>
<
>
<
>
>

output:

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

result:

ok yeah, seems ok, spent 9 queries of 15

Test #8:

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

input:

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

output:

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

result:

ok yeah, seems ok, spent 11 queries of 16

Test #9:

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

input:

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

output:

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

result:

ok yeah, seems ok, spent 13 queries of 18

Test #10:

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

input:

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

output:

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

result:

ok yeah, seems ok, spent 15 queries of 20

Test #11:

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

input:

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

output:

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

result:

ok yeah, seems ok, spent 17 queries of 21

Test #12:

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

input:

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

output:

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

result:

ok yeah, seems ok, spent 19 queries of 23

Test #13:

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

input:

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

output:

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

result:

ok yeah, seems ok, spent 21 queries of 25

Test #14:

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

input:

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

output:

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

result:

ok yeah, seems ok, spent 23 queries of 26

Test #15:

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

input:

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

output:

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

result:

ok yeah, seems ok, spent 25 queries of 28

Test #16:

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

input:

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

output:

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

result:

ok yeah, seems ok, spent 27 queries of 30

Test #17:

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

input:

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

output:

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

result:

ok yeah, seems ok, spent 29 queries of 31

Test #18:

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

input:

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

output:

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

result:

ok yeah, seems ok, spent 31 queries of 33

Test #19:

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

input:

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

output:

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

result:

ok yeah, seems ok, spent 33 queries of 35

Test #20:

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

input:

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

output:

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

result:

ok yeah, seems ok, spent 35 queries of 36

Test #21:

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

input:

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

output:

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

result:

ok yeah, seems ok, spent 37 queries of 38

Test #22:

score: -100
Wrong Answer
time: 3ms
memory: 3948kb

input:

111
>
>
>
>
>
>
>
>
>
>
<
>
>
>
<
>
>
>
<
>
<
>
>
>
>
>
<
>
<
>
<
>
>
>
>
>
<
>
>
>
>
>
>
>
<
>
>
>
<
>
>
>
<
>
>
>
>
>
>
>
<
>
>
>
>
>
>
>
<
>
>
>
>
>
>
>
>
>
<
>
<
>
<
>
<
>
>
>
<
>
<
>
<
>
>
>
>
>
>
>
>
>
<
>
>
>
<
>
<
>
<
>
<
>
<
>
>
>
>
>
<
>
>
>
>
>
<
>
>
>
>
>
>
>
>
>
>
>
>
>
<
>
<
>
<
>
<
>
...

output:

? 111 110
? 111 109
? 110 109
? 110 108
? 109 108
? 109 107
? 107 106
? 107 108
? 108 105
? 108 106
? 104 106
? 106 105
? 105 103
? 105 104
? 103 104
? 104 102
? 103 101
? 103 102
? 101 102
? 102 100
? 100 101
? 101 99
? 99 98
? 99 100
? 98 97
? 98 100
? 97 100
? 100 96
? 95 96
? 96 97
? 94 95
? 95 ...

result:

wrong answer didn't fit into 190 queries