QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#190607 | #3675. Interactive Array Guessing | Gamal74# | WA | 1ms | 3840kb | C++20 | 3.0kb | 2023-09-29 07:31:29 | 2023-09-29 07:31:30 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
#define fi first
#define se second
#define pp push_back
#define all(x) (x).begin(), (x).end()
#define Ones(n) __builtin_popcount(n)
#define mem(arrr, xx) memset(arrr,xx,sizeof arrr)
//#define int long long
#define debug(x) cout << (#x) << " = " << x << endl
void Gamal() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
}
int dx[] = {+0, +0, -1, +1, +1, +1, -1, -1};
int dy[] = {-1, +1, +0, +0, +1, -1, +1, -1};
const double EPS = 1e-9;
const ll OO = 0X3F3F3F3F3F3F3F3F;
const int N = 2e5 + 5, INF = INT_MAX, MOD = 1e9 + 7, LOG = 20;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<int> ask(vector<int> v) {
cout << "? " << v.size() << ' ';
for (auto x: v)cout << x + 1 << ' ';
cout << endl;
int sz;
cin >> sz;
vector<int> ret;
for (int i = 0; i < sz; ++i) {
int x;
cin >> x;
ret.push_back(x);
}
return ret;
}
void solve() {
int n;
cin >> n;
vector<int> p(n);
iota(all(p), 0);
shuffle(all(p), rng);
vector<vector<int>> ans(n);
vector<int> ind;
vector<int> pat;
int sz = 0;
for (int i = 0; i < n; ++i) {
if (sz >= 10) {
int j = i;
vector<int> nxt(p[j]);
while (j + 1 < n && nxt.size() + ind.size() + 1 <= n) {
for (auto x: ind)nxt.push_back(x);
j++;
nxt.push_back(p[j]);
}
vector<int> ret = ask(nxt);
vector<int>e(ret[0]);
int cur = i, ptr = 0;
for (int k = 1; k < ret.size() && cur < j; ++k) {
assert(k + pat.size() < ret.size());
bool ok = true;
for (int l = k; l < k + pat.size() && ok; ++l) {
ok &= pat[l - k] == ret[l];
}
if (ok) {
ans[p[cur]] = e;
e.clear();
cur++;
ptr = k + pat.size();
e.push_back(ret[ptr]);
k = ptr;
}
else {
e.push_back(ret[k]);
}
}
assert(cur == j);
for (int k = ptr; k < ret.size(); ++k) {
ans[p[j]].push_back(ret[k]);
}
i = j;
} else {
vector<int> ret = ask({p[i]});
ans[p[i]] = ret;
ind.push_back(p[i]);
for (auto x: ret)pat.push_back(x);
sz += ret.size();
}
}
cout << "! ";
for (int i = 0; i < n; ++i) {
cout << ans[i].size() << ' ';
for (auto x: ans[i])cout << x << ' ';
}
cout << endl;
}
signed main() {
Gamal();
int t = 1;
// cin >> t;
while (t--) {
solve();
}
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3840kb
input:
3 2 1 2 1 1 2 2 1
output:
? 1 2 ? 1 1 ? 1 3 ! 1 1 2 1 2 2 2 1
result:
ok 3 arrays, sum_len = 5
Test #2:
score: 0
Accepted
time: 1ms
memory: 3672kb
input:
3 1 2 3 1 4 2 2 2 3
output:
? 1 2 ? 1 3 ? 1 1 ! 2 2 3 1 2 3 1 4 2
result:
ok 3 arrays, sum_len = 6
Test #3:
score: 0
Accepted
time: 1ms
memory: 3776kb
input:
3 2 2 1 2 1 2 2 1 2
output:
? 1 3 ? 1 2 ? 1 1 ! 2 1 2 2 1 2 2 2 1
result:
ok 3 arrays, sum_len = 6
Test #4:
score: 0
Accepted
time: 1ms
memory: 3604kb
input:
1 1 3
output:
? 1 1 ! 1 3
result:
ok 1 arrays, sum_len = 1
Test #5:
score: 0
Accepted
time: 0ms
memory: 3568kb
input:
2 4 3 4 1 2 4 3 4 2 1
output:
? 1 1 ? 1 2 ! 4 3 4 1 2 4 3 4 2 1
result:
ok 2 arrays, sum_len = 8
Test #6:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
1 2 2 3
output:
? 1 1 ! 2 2 3
result:
ok 1 arrays, sum_len = 2
Test #7:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
2 1 1 1 1
output:
? 1 1 ? 1 2 ! 1 1 1 1
result:
ok 2 arrays, sum_len = 2
Test #8:
score: 0
Accepted
time: 1ms
memory: 3840kb
input:
3 2 2 1 2 1 2 2 1 2
output:
? 1 1 ? 1 2 ? 1 3 ! 2 2 1 2 1 2 2 1 2
result:
ok 3 arrays, sum_len = 6
Test #9:
score: 0
Accepted
time: 0ms
memory: 3668kb
input:
1 2 1 3
output:
? 1 1 ! 2 1 3
result:
ok 1 arrays, sum_len = 2
Test #10:
score: 0
Accepted
time: 1ms
memory: 3780kb
input:
1 2 1 2
output:
? 1 1 ! 2 1 2
result:
ok 1 arrays, sum_len = 2
Test #11:
score: -100
Wrong Answer
time: 1ms
memory: 3584kb
input:
9 2 2 3 2 1 4 1 2 2 2 3 2 2 4 1 2 16 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 15 2 3 2 3 2 3 1 4 2 2 3 2 4 2 1
output:
? 1 7 ? 1 4 ? 1 2 ? 1 1 ? 1 6 ? 1 8 ? 8 1 1 1 1 1 1 1 1 ? 9 1 1 7 4 2 1 6 8 5 ! 2 2 3 1 2 5 0 0 3 2 3 2 1 4 1 1 2 2 4 2 2 3 1 2 16 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3
result:
wrong answer Length of 3-th array differ: expected 3, found 5