QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#191502 | #7535. Limited Shuffle Restoring | Days_of_Future_Past# | WA | 1ms | 3988kb | C++14 | 1.9kb | 2023-09-30 00:05:23 | 2023-09-30 00:05:23 |
Judging History
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]