QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#309596 | #7535. Limited Shuffle Restoring | 8BQube | WA | 4ms | 3972kb | C++20 | 3.3kb | 2024-01-20 18:53:00 | 2024-01-20 18:53:00 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define X first
#define Y second
#define SZ(a) ((int)a.size())
#define ALL(v) v.begin(), v.end()
#define pb push_back
vector<vector<int>> pool;
map<vector<int>, pii> decision;
map<vector<int>, int> step;
int get_decision(const vector<int> &q) {
if (SZ(q) == 1) return 0;
if (decision.find(q) != decision.end())
return step[q];
int ans = 100;
for (int i = 0; i < 5; ++i)
for (int j = i + 1; j < 5; ++j) {
if (SZ(q) == SZ(pool) && (i != 3 || j != 4)) {
continue;
}
vector<int> lft, rgt;
for (int k : q)
if (pool[k][i] < pool[k][j])
lft.pb(k);
else
rgt.pb(k);
if (lft.empty() || rgt.empty()) continue;
int lval = get_decision(lft);
int rval = get_decision(rgt);
if (ans > max(lval, rval) + 1) {
ans = max(lval, rval) + 1;
decision[q] = pii(i, j);
}
}
return step[q] = ans;
}
map<pii, int> mem;
int cmp(int l, int r) {
int flag = 0;
if (l > r) swap(l, r), flag = 1;
if (mem.find(pii(l, r)) != mem.end())
return mem[pii(l, r)] ^ flag;
cout << "? " << l << " " << r << endl;
char c;
cin >> c;
return (mem[pii(l, r)] = int(c == '<')) ^ flag;
}
int pos[10], ans[100005], pl[1000005];
vector<int> solve(vector<int> cur) {
while (SZ(cur) > 1) {
auto [l, r] = decision[cur];
vector<int> nxt;
int res = cmp(pos[l + 1], pos[r + 1]);
for (int k : cur)
if ((pool[k][l] < pool[k][r]) == res)
nxt.pb(k);
cur.swap(nxt);
}
return pool[cur[0]];
}
int main() {
ios::sync_with_stdio(0), cin.tie(0);
vector<int> perm(5);
iota(ALL(perm), 1);
for (int i = 0; i <= 2; i++)
for (int j = 1; j <= 3; j++)
for (int k = 2; k <= 4; k++)
for (int l = 3; l <= 4; l++) {
vector<int> tmp = perm;
swap(tmp[0], tmp[i]);
swap(tmp[1], tmp[j]);
swap(tmp[2], tmp[k]);
swap(tmp[3], tmp[l]);
pool.pb(tmp);
}
vector<int> all(SZ(pool));
iota(ALL(all), 0);
get_decision(all);
int n, orgn;
cin >> n, orgn = n;
if (n == 1) return cout << "! 1\n", 0;
pos[4] = n - 1, pos[5] = n;
while (n >= 5) {
for (int i = 1; i <= 3; ++i)
pos[i] = n - 5 + i;
auto res = solve(all);
for (int i = 0; i < 5; ++i)
cerr << res[i] << " \n"[i == 4];
for (int i = 0; i < 5; ++i)
ans[res[i]] = pos[i + 1];
pos[4] = ans[n - 4], pos[5] = ans[n - 3];
n -= 3;
}
vector<int> idx;
for (int i = 1; i <= n - 2; ++i)
idx.pb(i);
idx.pb(pos[4]), idx.pb(pos[5]);
sort(ALL(idx), cmp);
for (int i = 0; i < SZ(idx); ++i)
ans[i + 1] = idx[i];
for (int i = 1; i <= orgn; ++i)
pl[ans[i]] = i;
cout << "!";
for (int i = 1; i <= orgn; ++i)
cout << " " << pl[i];
cout << "\n";
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3972kb
input:
5 > < < > < <
output:
? 4 5 ? 1 5 ? 3 5 ? 1 3 ? 1 2 ? 2 5 ! 2 3 1 5 4
result:
ok yeah, seems ok, spent 6 queries of 13
Test #2:
score: 0
Accepted
time: 0ms
memory: 3764kb
input:
1
output:
! 1
result:
ok yeah, seems ok, spent 0 queries of 6
Test #3:
score: 0
Accepted
time: 3ms
memory: 3656kb
input:
2 >
output:
? 1 2 ! 2 1
result:
ok yeah, seems ok, spent 1 queries of 8
Test #4:
score: 0
Accepted
time: 4ms
memory: 3788kb
input:
3 > < >
output:
? 1 2 ? 2 3 ? 1 3 ! 3 1 2
result:
ok yeah, seems ok, spent 3 queries of 10
Test #5:
score: 0
Accepted
time: 4ms
memory: 3764kb
input:
4 < < > < > >
output:
? 1 2 ? 1 3 ? 2 3 ? 1 4 ? 2 4 ? 3 4 ! 1 4 3 2
result:
ok yeah, seems ok, spent 6 queries of 11
Test #6:
score: 0
Accepted
time: 4ms
memory: 3948kb
input:
5 > < > > > >
output:
? 4 5 ? 1 5 ? 3 5 ? 2 5 ? 3 4 ? 2 4 ! 1 4 5 3 2
result:
ok yeah, seems ok, spent 6 queries of 13
Test #7:
score: -100
Wrong Answer
time: 4ms
memory: 3784kb
input:
6 > < > > > > < <
output:
? 5 6 ? 2 6 ? 4 6 ? 3 6 ? 4 5 ? 3 5 ? 1 6 ? 1 5 ! 1 0 4 5 3 2
result:
wrong answer Integer element [index=2] equals to 0, violates the range [1, 6]