QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#190601#3675. Interactive Array GuessingGamal74#RE 1ms3496kbC++202.9kb2023-09-29 07:22:232023-09-29 07:22:24

Judging History

This is the latest submission verdict.

  • [2023-09-29 07:22:24]
  • Judged
  • Verdict: RE
  • Time: 1ms
  • Memory: 3496kb
  • [2023-09-29 07:22:23]
  • Submitted

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 >= 9) {
            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);
            int cur = i, ptr = 0;
            for (int k = 1; k < n && cur < j; ++k) {
                assert(k + pat.size() < n);
                bool ok = true;
                for (int l = k; l < k + pat.size() && ok; ++l) {
                    ok |= pat[l - k] == ret[l];
                }
                if (ok) {
                    for (int l = ptr; l < k; ++l) {
                        ans[p[cur]].push_back(ret[l]);
                    }
                    cur++;
                    ptr = k + pat.size();
                    k = ptr;
                }
            }
            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();
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3468kb

input:

3
2 1 2
2 2 1
1 1

output:

? 1 2 
? 1 3 
? 1 1 
! 1 1 2 1 2 2 2 1 

result:

ok 3 arrays, sum_len = 5

Test #2:

score: 0
Accepted
time: 1ms
memory: 3476kb

input:

3
3 1 4 2
1 2
2 2 3

output:

? 1 3 
? 1 2 
? 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: 3496kb

input:

3
2 1 2
2 1 2
2 2 1

output:

? 1 2 
? 1 1 
? 1 3 
! 2 1 2 2 1 2 2 2 1 

result:

ok 3 arrays, sum_len = 6

Test #4:

score: 0
Accepted
time: 0ms
memory: 3352kb

input:

1
1 3

output:

? 1 1 
! 1 3 

result:

ok 1 arrays, sum_len = 1

Test #5:

score: 0
Accepted
time: 0ms
memory: 3368kb

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: 3476kb

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: 3476kb

input:

2
1 1
1 1

output:

? 1 2 
? 1 1 
! 1 1 1 1 

result:

ok 2 arrays, sum_len = 2

Test #8:

score: 0
Accepted
time: 0ms
memory: 3360kb

input:

3
2 2 1
2 1 2
2 1 2

output:

? 1 1 
? 1 3 
? 1 2 
! 2 2 1 2 1 2 2 1 2 

result:

ok 3 arrays, sum_len = 6

Test #9:

score: 0
Accepted
time: 1ms
memory: 3476kb

input:

1
2 1 3

output:

? 1 1 
! 2 1 3 

result:

ok 1 arrays, sum_len = 2

Test #10:

score: 0
Accepted
time: 0ms
memory: 3468kb

input:

1
2 1 2

output:

? 1 1 
! 2 1 2 

result:

ok 1 arrays, sum_len = 2

Test #11:

score: -100
Runtime Error

input:

9
2 2 3
1 1
1 2
1 1
2 1 4
1 2
3 1 4 2
13 2 3 1 2 1 1 4 2 1 4 2 2 4

output:

? 1 7 
? 1 5 
? 1 2 
? 1 9 
? 1 4 
? 1 8 
? 1 3 
? 8 7 5 2 9 4 8 3 6 

result: