QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#191502#7535. Limited Shuffle RestoringDays_of_Future_Past#WA 1ms3988kbC++141.9kb2023-09-30 00:05:232023-09-30 00:05:23

Judging History

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

  • [2023-09-30 00:05:23]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3988kb
  • [2023-09-30 00:05:23]
  • 提交

answer

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

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

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

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

  if (ONLINE) {
    scanf("%s", buf);
    return buf[0] == '<';
  } else {
    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]);
  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;
  }
  vector<int> ans(n + 1);
  set<int> cand;
  for (int i = n; i > 0 && i >= n-2; --i)
    cand.insert(i);
  for (int i = n; i > 0; --i) {
    int mx_i = argmax(cand);
    ans[mx_i] = i;
    cand.erase(mx_i);
    if (i - 3 > 0)
      cand.insert(i - 3);
  }
  answer(ans);
}

int main() {
  //build();
  int tc = 1;
  while (tc--) {
    main2();
  }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:


output:

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

result:

ok yeah, seems ok, spent 6 queries of 13

Test #2:

score: -100
Wrong Answer
time: 0ms
memory: 3988kb

input:


output:

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

result:

wrong answer Integer 3 violates the range [1, 1]