QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#686375 | #9432. Permutation | xydCatGirl# | RE | 1ms | 3692kb | C++20 | 3.3kb | 2024-10-29 11:53:38 | 2024-10-29 11:53:39 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define pb emplace_back
#define For(i, x, y) for (int i = (x); i <= (y); i ++)
#define rep(i, x, y) for (int i = (x); i >= (y); i --)
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
#define sz(v) (int)((v).size())
#define ull unsigned long long
#define ls (p << 1)
#define rs (p << 1 | 1)
#define mp make_pair
#define i128 __int128
#define db long double
#define vi vector< int >
#define mem(v, x) memset(v, x, sizeof(v))
#define A3 array< int, 3 >
#define A4 array< int, 4 >
#define vpii vector< pair< int, int > >
using namespace std;
mt19937_64 rnd(time(0));
template< typename T > void cmin(T &x, T y) { return x = min(x, y), void(); }
template< typename T > void cmax(T &x, T y) { return x = max(x, y), void(); }
int ksm(int x, int y, int p) {
int v = 1; x %= p;
while (y) v = 1ll * v * ((y & 1) ? x : 1) % p, x = 1ll * x * x % p, y >>= 1;
return (v % p + p) % p;
}
bool MemoryST;
const int N = 1005;
const int mod = 998244353;
const long long INF = 1e18;
const int base = 13131;
int n;
int ans[N], q[N];
int query() {
cout << "0 ";
For (i, 1, n) cout << q[i] << ' ';
cout << endl;
int res; cin >> res;
return res;
}
bool del[N];
void solve(int l, int r, vi a) {
if (l == r) return ans[l] = a[0], void();
int mid = (l + r) >> 1;
while (1) {
shuffle(all(a), rnd);
int x = a[0], y = a[1];
For (p, l, mid) q[p] = x;
For (p, mid + 1, r) q[p] = y;
For (p, 1, l - 1) q[p] = x;
For (p, r + 1, n) q[p] = y;
int res = query();
if (res != 1) break;
}
vi b, c;
for (int i = 0; i + 1 < sz(a); i += 2) {
int x = a[i], y = a[i + 1];
For (p, l, mid) q[p] = x;
For (p, mid + 1, r) q[p] = y;
For (p, 1, l - 1) q[p] = x;
For (p, r + 1, n) q[p] = y;
int res = query();
if (res == 2) b.pb(x), c.pb(y);
else if (res == 0) b.pb(y), c.pb(x);
else {
for (int x : a) del[x] = 1;
int z = 1;
while (del[z]) z ++;
for (int x : a) del[x] = 0;
For (p, l, mid) q[p] = x;
For (p, 1, l - 1) q[p] = x;
For (p, r + 1, n) q[p] = x;
if (r - l + 1 != n) {
For (p, mid + 1, r) q[p] = z;
res = query();
if (res) b.pb(x), b.pb(y);
else c.pb(x), c.pb(y);
} else {
if (sz(b)) {
z = b[0];
For (p, mid + 1, r) q[p] = z;
res = query();
if (res) b.pb(x), b.pb(y);
else c.pb(x), c.pb(y);
} else {
z = c[0];
For (p, mid + 1, r) q[p] = z;
res = query();
if (res == 2) b.pb(x), b.pb(y);
else c.pb(x), c.pb(y);
}
}
}
}
if ((r - l + 1) % 2) {
int x = a[sz(a) - 1];
if (sz(b) != mid - l + 1) b.pb(x);
else c.pb(x);
}
solve(l, mid, b); solve(mid + 1, r, c);
return;
}
void Main() {
cin >> n; vi a;
For (i, 1, n) a.pb(i);
solve(1, n, a);
cout << "1 ";
For (i, 1, n) cout << ans[i] << ' ';
cout << endl;
return;
}
bool MemoryED;
signed main() {
ios :: sync_with_stdio(0);
cin.tie(0); cout.tie(0);
// cerr << fixed << setprecision(6) << (&MemoryST - &MemoryED) / 1048576.0 << "MB\n";
int TESTCNT = 1;
// cin >> TESTCNT;
while (TESTCNT --) Main();
// cerr << endl << 1e3 * clock() / CLOCKS_PER_SEC << "ms";
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3692kb
input:
5 1 1 1 1 0 0 1 1 1 1 0 0 0 0 2 2
output:
0 2 2 2 3 3 0 5 5 5 1 1 0 4 4 4 2 2 0 2 2 2 4 4 0 5 5 5 3 3 0 5 5 5 3 3 0 4 4 4 2 2 0 4 4 4 3 3 0 3 3 4 4 4 0 3 3 4 4 4 0 2 2 4 4 4 0 2 2 4 4 4 0 4 3 3 3 3 0 4 3 3 3 3 0 1 1 1 1 5 0 1 1 1 1 5 1 3 4 2 1 5
result:
ok Accepted
Test #2:
score: -100
Runtime Error
input:
1000 0 0 0 1 0 1 1 0 1 0 0 2 1 1 2 1 1 1 1 0 1 1 1 1 2 1 0 1 1 1 1 2 1 1 2 1 1 0 2 1 1 2 0 0 1 0 2 1 1 1 0 1 1 1 0 1 0 1 1 1 0 1 0 2 1 1 1 0 1 0 2 0 1 0 2 1 0 1 0 1 1 2 2 0 1 0 0 1 1 0 1 0 0 1 0 1 1 1 0 1 0 2 0 0 1 0 1 1 0 1 1 1 0 0 0 1 0 2 0 2 1 0 1 1 1 0 0 0 2 1 0 1 1 1 0 1 0 1 1 1 0 1 1 2 2 2 1 0...
output:
0 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 62...