oj.uz

Submission #1085830

# Submission time Handle Problem Language Result Execution time Memory
1085830 2024-09-08T19:31:09 Z contest_alt Carnival (CEOI14_carnival) C++17
100 / 100
 5 ms 596 KB 
#include <stdio.h>
#include <vector>
#include <algorithm>

const int MAXN = 150;

int query( const std::vector<int> &indici ) {
  printf( "%d", (int)indici.size() );
  for( int x : indici )
    printf( " %d", x + 1 );
  printf( "\n" );
  fflush( stdout );

  int ret;
  scanf( "%d", &ret );
  return ret;
}

int non_uniq( const std::vector<int> &indici ) {
  return (int)indici.size() - query( indici );
}

int col[MAXN];

int main() {
  int n;
  scanf( "%d", &n );

  std::vector<int> reps;
  std::vector<int> others;
  for( int i = 0; i < n; i++ ){
    reps.push_back( i );
    if( non_uniq( reps ) ){
      reps.pop_back();
      others.push_back( i );
    }
  }

  for( int i = 0; i < (int)reps.size(); i++ )
    col[reps[i]] = i + 1;

  for( int idx : others ) {
    int st = 0, dr = (int)reps.size();

    while( dr - st > 1 ){
      int mij = (st + dr) >> 1;

      std::vector<int> left_query(1, idx);
      for( int i = st; i < mij; i++ )
        left_query.push_back( reps[i] );

      if( non_uniq( left_query ) ) // repreat found => go in left half
        dr = mij;
      else
        st = mij;
    }

    col[idx] = col[reps[st]];
  }

  printf( "0" );
  for( int i = 0; i < n; i++ )
    printf( " %d", col[i] );
  printf( "\n" );
  
  return 0;
}

Compilation message

carnival.cpp: In function 'int query(const std::vector<int>&)':
carnival.cpp:15:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |   scanf( "%d", &ret );
      |   ~~~~~^~~~~~~~~~~~~~
carnival.cpp: In function 'int main()':
carnival.cpp:27:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |   scanf( "%d", &n );
      |   ~~~~~^~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 3 ms 344 KB Output is correct
3 Correct 3 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 4 ms 596 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 5 ms 344 KB Output is correct
3 Correct 3 ms 344 KB Output is correct
4 Correct 2 ms 344 KB Output is correct
5 Correct 3 ms 344 KB Output is correct
6 Correct 2 ms 344 KB Output is correct
7 Correct 3 ms 344 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 3 ms 344 KB Output is correct
3 Correct 4 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 3 ms 344 KB Output is correct
6 Correct 3 ms 344 KB Output is correct
7 Correct 4 ms 344 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 3 ms 344 KB Output is correct
3 Correct 3 ms 344 KB Output is correct
4 Correct 2 ms 344 KB Output is correct
5 Correct 4 ms 344 KB Output is correct
6 Correct 3 ms 344 KB Output is correct
7 Correct 4 ms 344 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 3 ms 344 KB Output is correct
3 Correct 3 ms 344 KB Output is correct
4 Correct 3 ms 344 KB Output is correct
5 Correct 3 ms 344 KB Output is correct
6 Correct 3 ms 344 KB Output is correct
7 Correct 2 ms 424 KB Output is correct