oj.uz

Submission #447291

# Submission time Handle Problem Language Result Execution time Memory
447291 2021-07-25T20:29:40 Z LucaIlie Library (JOI18_library) C++17
100 / 100
 352 ms 412 KB 
#include <vector>
#include <stdio.h>
#include <library.h>

using namespace std;

int n;
vector<int> v, tak, res;

/*int Query( vector<int> m ) {
    int ans, i;

    for ( i = 0; i < n; i++ ) {
        if ( m[i] == 1 )
            printf( "%d ", i + 1 );
    }
    printf( "\n" );

    scanf( "%d", &ans );

    return ans;
}

void Answer( vector<int> m ) {
    int i;

    for ( i = 0; i < n; i++ )
        printf( "%d ", m[i] );
}*/

void Solve( int n ) {
    int ans, p, st, dr, mij, i, j;

    if ( n == 1 )
        res.push_back( 1 );
    else {
        for ( i = 0; i < n; i++ )
            v.push_back( i );

        for ( i = 0; i < n; i++ )
            tak.push_back( 1 );
        ans = 2;
        i = 0;
        while ( ans == 2 ) {
            tak[v[i]] = 0;
            ans = Query( tak );
            tak[v[i]] = 1;
            i++;
        }
        res.push_back( v[i - 1] + 1 );
        p = i - 1;

        for ( i = 1; i < n; i++ ) {
            for ( j = p; j < n - (i - 1); j++ )
                v[j] = v[j + 1];
            st = 0;
            dr = n - i;
            while ( dr - st > 1 ) {
                mij = (st + dr) / 2;

                for ( j = 0; j < n; j++ )
                    tak[j] = 0;
                for ( j = st; j < mij; j++ )
                    tak[v[j]] = 1;
                ans = Query( tak );
                tak[res[i - 1] - 1] = 1;
                if ( Query( tak ) == ans )
                    dr = mij;
                else
                    st = mij;
            }
            res.push_back( v[st] + 1 );
            p = st;
        }
    }

    Answer( res );
}

/*int main() {
    scanf( "%d", &n );
    Solve( n );
    return 0;
}*/

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 256 KB # of queries: 2375
2 Correct 45 ms 200 KB # of queries: 2409
3 Correct 46 ms 200 KB # of queries: 2648
4 Correct 41 ms 200 KB # of queries: 2595
5 Correct 27 ms 200 KB # of queries: 2508
6 Correct 38 ms 200 KB # of queries: 2551
7 Correct 38 ms 200 KB # of queries: 2544
8 Correct 39 ms 200 KB # of queries: 2420
9 Correct 43 ms 200 KB # of queries: 2546
10 Correct 22 ms 200 KB # of queries: 1474
11 Correct 0 ms 200 KB # of queries: 0
12 Correct 0 ms 200 KB # of queries: 1
13 Correct 1 ms 200 KB # of queries: 4
14 Correct 1 ms 200 KB # of queries: 7
15 Correct 2 ms 200 KB # of queries: 77
16 Correct 3 ms 200 KB # of queries: 183

Subtask #2
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 256 KB # of queries: 2375
2 Correct 45 ms 200 KB # of queries: 2409
3 Correct 46 ms 200 KB # of queries: 2648
4 Correct 41 ms 200 KB # of queries: 2595
5 Correct 27 ms 200 KB # of queries: 2508
6 Correct 38 ms 200 KB # of queries: 2551
7 Correct 38 ms 200 KB # of queries: 2544
8 Correct 39 ms 200 KB # of queries: 2420
9 Correct 43 ms 200 KB # of queries: 2546
10 Correct 22 ms 200 KB # of queries: 1474
11 Correct 0 ms 200 KB # of queries: 0
12 Correct 0 ms 200 KB # of queries: 1
13 Correct 1 ms 200 KB # of queries: 4
14 Correct 1 ms 200 KB # of queries: 7
15 Correct 2 ms 200 KB # of queries: 77
16 Correct 3 ms 200 KB # of queries: 183
17 Correct 323 ms 288 KB # of queries: 17982
18 Correct 349 ms 284 KB # of queries: 17293
19 Correct 344 ms 288 KB # of queries: 17467
20 Correct 307 ms 288 KB # of queries: 16325
21 Correct 251 ms 200 KB # of queries: 15324
22 Correct 338 ms 412 KB # of queries: 17669
23 Correct 352 ms 200 KB # of queries: 17224
24 Correct 149 ms 412 KB # of queries: 7915
25 Correct 331 ms 320 KB # of queries: 17136
26 Correct 254 ms 200 KB # of queries: 15963
27 Correct 113 ms 200 KB # of queries: 8040
28 Correct 254 ms 300 KB # of queries: 15957
29 Correct 240 ms 284 KB # of queries: 15939
30 Correct 267 ms 200 KB # of queries: 15957