QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#190590#3675. Interactive Array GuessingAnwar#RE 1ms3488kbC++232.6kb2023-09-29 07:08:282023-09-29 07:08:28

Judging History

This is the latest submission verdict.

  • [2023-09-29 07:08:28]
  • Judged
  • Verdict: RE
  • Time: 1ms
  • Memory: 3488kb
  • [2023-09-29 07:08:28]
  • Submitted

answer

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int N = 2e5 + 3, MOD = 998244353;//1e9 + 7;


int main() {

    cin.tie(0);cin.sync_with_stdio(0);
    cout.tie(0);cout.sync_with_stdio(0);

    int n;
    cin >> n;

    if(n <= 20)
    {
        vector<int> ans ;

        for (int i = 1; i <= n; ++i) {
            cout << "? " << 1 << " " << i << endl ;

            int k ;
            cin >> k;
            ans.push_back(k) ;
            for (int j = 0; j < k; ++j) {
                int x;
                cin >> x;
                ans.push_back(x) ;
            }
        }

        cout << "! " ;
        for(int ch : ans ) cout << ch << " " ;

        return 0 ;
    }

    vector<int> ids ;

    vector<bool> taken(n+1) ;

    while ( (int)ids.size() < 18)
    {
        int id = rand()%n + 1;
        while (taken[id]) id = rand()%n + 1;

        taken[id] =1 ;

        ids.push_back(id) ;
    }

    cout << "? " << 18 << " " ;

    for(int id : ids) cout << id << " " ;
    cout << endl ;

    int sz ;
    cin >> sz ;
    vector<int> v(sz) ;

    for (int i = 0; i < sz; ++i) {
        cin >> v[i] ;
    }

    int final = 1;

    vector<int> ans[n+1];

    while (final <= n)
    {
        vector<int> ask ;
        ask.push_back(final++) ;

        while ( final <= n  && (int)ask.size() + 19 <= n  )
        {
            for(int id : ids) ask.push_back(id) ;
            ask.push_back(final++ );
        }

        cout << "? " << (int)ask.size() << " " ;
        for(int ch : ask) cout << ch << " " ;
        cout << endl ;

        int sz2 ;
        cin >> sz2 ;
        vector<int> vv(sz2) ;
        for (int i = 0; i < sz2; ++i) {
            cin >> vv[i] ;
        }

        vector<int> del ;

        for(int i =1 ; i < sz2 - 1 ; i ++)
        {
            int j = 0 ;

            while (j < sz && v[j] == vv[i+j])j++ ;

            if(j == sz)
            {
                del.push_back(i) ;

                i += sz ;
            }
        }

        del.push_back(sz2) ;

        int j =0 , k =0 ;

        for(int i = 0 ; i < (int)ask.size() ; i += 19)
        {
            while (j != del[k] )
            {
                ans[ask[i]].push_back(vv[j]) ;

                j++ ;
            }
            
            j += sz2 ;

            k++ ;
        }
    }

    cout << "! " ;

    for(int i= 1; i <= n; i++)
    {
        cout << (int)ans[i].size() << " " ;
        for(int ch : ans[i]) cout << ch << " " ;
    }


    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3
1 1
2 1 2
2 2 1

output:

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

result:

ok 3 arrays, sum_len = 5

Test #2:

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

input:

3
2 2 3
1 2
3 1 4 2

output:

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

result:

ok 3 arrays, sum_len = 6

Test #3:

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

input:

3
2 1 2
2 1 2
2 2 1

output:

? 1 1
? 1 2
? 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: 1ms
memory: 3392kb

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: 1ms
memory: 3484kb

input:

1
2 2 3

output:

? 1 1
! 2 2 3 

result:

ok 1 arrays, sum_len = 2

Test #7:

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

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: 0ms
memory: 3408kb

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

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

input:

1
2 1 2

output:

? 1 1
! 2 1 2 

result:

ok 1 arrays, sum_len = 2

Test #11:

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

input:

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

output:

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

result:

ok 9 arrays, sum_len = 15

Test #12:

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

input:

10
2 1 2
2 1 2
2 2 1
2 2 1
1 1
2 1 2
1 1
2 2 1
1 2
1 2

output:

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

result:

ok 10 arrays, sum_len = 16

Test #13:

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

input:

3
1 3
1 2
1 2

output:

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

result:

ok 3 arrays, sum_len = 3

Test #14:

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

input:

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

output:

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

result:

ok 9 arrays, sum_len = 27

Test #15:

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

input:

1
8 369 876 138 664 45 749 540 971

output:

? 1 1
! 8 369 876 138 664 45 749 540 971 

result:

ok 1 arrays, sum_len = 8

Test #16:

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

input:

1
1 913

output:

? 1 1
! 1 913 

result:

ok 1 arrays, sum_len = 1

Test #17:

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

input:

1
1 177

output:

? 1 1
! 1 177 

result:

ok 1 arrays, sum_len = 1

Test #18:

score: -100
Runtime Error

input:

57
27 3 3 4 3 4 2 1 2 4 2 1 1 3 1 1 4 3 2 4 3 1 1 3 4 2 3 4
58 1 2 3 3 4 3 4 2 1 2 4 2 1 1 3 1 1 4 3 2 4 3 1 1 3 4 2 3 4 3 3 3 4 3 4 2 1 2 4 2 1 1 3 1 1 4 3 2 4 3 1 1 3 4 2 3 4 1

output:

? 18 41 35 4 23 30 47 11 31 22 8 21 29 46 37 44 54 28 13 
? 39 1 41 35 4 23 30 47 11 31 22 8 21 29 46 37 44 54 28 13 2 41 35 4 23 30 47 11 31 22 8 21 29 46 37 44 54 28 13 3 

result: