oj.uz

Submission #130289

# Submission time Handle Problem Language Result Execution time Memory
130289 2019-07-14T16:58:38 Z DodgeBallMan Carnival (CEOI14_carnival) C++14
100 / 100
 26 ms 404 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 200;
int n, c, mark[N];
vector<int> all;
int ask( vector<int> v ) {
    int ret;
    printf("%d ",v.size() );
    for( int i = 0 ; i < ( int )v.size() - 1 ; i++ ) printf("%d ",v[i]);
    printf("%d\n",v[(int)v.size()-1]);
    fflush( stdout );
    scanf("%d",&ret);
    return ret;
}

void process( int l, int r, int nu ) {
    //printf("L : %d R : %d\n",l,r);
    if( l == r ) {
        vector<int> t;
        t.emplace_back( all[l] ), t.emplace_back( nu );
        if( ask( t ) == 1 ) mark[all[l]] = c; 
        return ;
    }
    int mid = ( l + r ) >> 1;
    vector<int> v, v2;
    for( int i = l ; i <= mid ; i++ ) v.emplace_back( all[i] );
    for( int i = mid+1 ; i <= r ; i++ ) v2.emplace_back( all[i] );
    int a = ask( v ), b = ask( v2 );
    v.emplace_back( nu ), v2.emplace_back( nu );
    int c = ask( v ), d = ask( v2 );
    //printf("%d %d %d %d\n",a,b,c,d);
    if( c == 1 ) for( int i = 0 ; i < v.size() ; i++ ) mark[v[i]] = mark[nu];
    if( d == 1 ) for( int i = 0 ; i < v2.size() ; i++ ) mark[v2[i]] = mark[nu];
    if( a == c && c != 1 ) process( l, mid, nu );
    if( b == d && d != 1 ) process( mid + 1, r, nu );
}

int main()
{
    scanf("%d",&n);
    for( int i = 1 ; i <= n ; i++ ) all.emplace_back( i );
    for( int i = 1 ; i <= n ; i++ ) if( !mark[i] ) {
        ++c;
        all.erase( all.begin() );
        mark[i] = c;
        int x = all.size();
        if( x == 0 ) break;
        process( 0, x-1, i );
        all.clear();
        for( int j = 1 ; j <= n ; j++ ) if( !mark[j] ) all.emplace_back( j );
        //printf("END\n");
    }
    printf("0 ");
    for( int i = 1 ; i <= n ; i++ ) printf("%d ",mark[i]);
    return 0;
}

Compilation message

carnival.cpp: In function 'int ask(std::vector<int>)':
carnival.cpp:10:27: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
     printf("%d ",v.size() );
                  ~~~~~~~~ ^
carnival.cpp: In function 'void process(int, int, int)':
carnival.cpp:34:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if( c == 1 ) for( int i = 0 ; i < v.size() ; i++ ) mark[v[i]] = mark[nu];
                                   ~~^~~~~~~~~~
carnival.cpp:35:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if( d == 1 ) for( int i = 0 ; i < v2.size() ; i++ ) mark[v2[i]] = mark[nu];
                                   ~~^~~~~~~~~~~
carnival.cpp: In function 'int ask(std::vector<int>)':
carnival.cpp:14:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&ret);
     ~~~~~^~~~~~~~~~~
carnival.cpp: In function 'int main()':
carnival.cpp:42:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 376 KB Output is correct
2 Correct 11 ms 376 KB Output is correct
3 Correct 18 ms 380 KB Output is correct
4 Correct 11 ms 380 KB Output is correct
5 Correct 7 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 20 ms 376 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 308 KB Output is correct
2 Correct 23 ms 252 KB Output is correct
3 Correct 14 ms 248 KB Output is correct
4 Correct 8 ms 248 KB Output is correct
5 Correct 9 ms 248 KB Output is correct
6 Correct 4 ms 376 KB Output is correct
7 Correct 16 ms 404 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 16 ms 248 KB Output is correct
3 Correct 13 ms 248 KB Output is correct
4 Correct 7 ms 248 KB Output is correct
5 Correct 11 ms 248 KB Output is correct
6 Correct 8 ms 248 KB Output is correct
7 Correct 26 ms 376 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 376 KB Output is correct
2 Correct 14 ms 252 KB Output is correct
3 Correct 15 ms 376 KB Output is correct
4 Correct 12 ms 248 KB Output is correct
5 Correct 9 ms 248 KB Output is correct
6 Correct 10 ms 376 KB Output is correct
7 Correct 24 ms 376 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 376 KB Output is correct
2 Correct 21 ms 376 KB Output is correct
3 Correct 12 ms 376 KB Output is correct
4 Correct 11 ms 248 KB Output is correct
5 Correct 8 ms 296 KB Output is correct
6 Correct 11 ms 376 KB Output is correct
7 Correct 8 ms 248 KB Output is correct