oj.uz

Submission #446079

# Submission time Handle Problem Language Result Execution time Memory
446079 2021-07-20T18:30:14 Z raid Library (JOI18_library) C++17
0 / 100
 59 ms 200 KB 
#include "library.h"
#include <iostream>
#include <vector>
#define pb push_back

using namespace std;

void Solve( int n ) {
  vector<int> bk, a, x, y, sol, pos;
  int ext, lg = 0;

  for ( int i = 1; i <= n; ++i ) {
	a.pb( 0 );
	x.pb( 0 );
	y.pb( 0 );
	bk.pb( 0 );
  }
  int p = n;
  while ( p ) {
	p >>= 1;
    ++lg;
  }
  --lg;

  ext = 0;
  for ( int i = 0; i <= lg; ++i ) {
	for ( int j = 1; j <= n; ++j ) {
	  x[j - 1] = ((j & (1 << i)) >> i);
	  y[j - 1] = x[j - 1] ^ 1;
	}
	int qx = Query( x ), qy = Query( y );
	if ( qx > qy ) {
	  ext += (1 << i);
	} else if ( qx == qy ) {
	  pos.pb( i );
	}
	for ( int j = 1; j <= n; ++j ) {
      x[j - 1] = y[j - 1] = 0;
	}
  }
  ext += (1 << pos[0]);
  int bt = 1;
  for ( int i = 1; i < pos.size(); ++i ) {
	int p1 = pos[i - 1], p2 = pos[i], cnt1 = 0, cnt2 = 0;
    for ( int j = 1; j <= n; ++j ) {
	  if ( ((j & (1 << p1)) >> p1) == ((j & (1 << p2)) >> p2) ) {
        x[j - 1] = 1;
		++cnt1;
	  } else {
		y[j - 1] = 1;
	    ++cnt2;
	  }
	}
	if ( !cnt2 ) {
	  ext += bt * (1 << p2);
	  continue;
	}
	if ( !cnt1 ) {
	  bt ^= 1;
	  ext += bt * (1 << p2);
	  continue;
	}
	int qx = Query( x ), qy = Query( y );
	if ( qx > qy ) {
	  ext += bt * (1 << p2);
	} else {
	  bt ^= 1;
	  ext += bt * (1 << p2);
	}
	for ( int j = 1; j <= n; ++j ) {
	  x[j - 1] = y[j - 1] = 0;
	}
  }
  a[ext - 1] = x[ext - 1] = 1;
  sol.pb( ext );
  for ( int i = 2; i < n; ++i ) {
	int res = 0;
	for ( int b = 0; b <= lg; ++b ) {
	  int cnt = 0;
	  for ( int j = 1; j <= n; ++j ) {
	    if ( (j & (1 << b)) && !x[j - 1] ) {
		  y[j - 1] = 1;
		  x[j - 1] = 1;
		  ++cnt;
		}
	  }
	  if ( cnt ) {
	    if ( Query( x ) == Query( y ) ) {
		 res += (1 << b);
	    }
	  }
	  for ( int j = 1; j <= n; ++j ) {
		x[j - 1] = a[j - 1];
		y[j - 1] = 0;
	  }
	}
	a[res - 1] = 1;
    x[res - 1] = 1;
	sol.pb( res );
  }
  for ( int i = 1; i <= n; ++i ) {
	if ( a[i - 1] == 0 ) {
	  sol.pb( i );
	}
  }
  Answer( sol );
}

Compilation message

library.cpp: In function 'void Solve(int)':
library.cpp:43:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |   for ( int i = 1; i < pos.size(); ++i ) {
      |                    ~~^~~~~~~~~~~~

Subtask #1
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 200 KB # of queries: 3030
2 Correct 54 ms 200 KB # of queries: 3022
3 Correct 59 ms 200 KB # of queries: 3180
4 Correct 47 ms 200 KB # of queries: 3174
5 Correct 59 ms 200 KB # of queries: 3176
6 Correct 51 ms 200 KB # of queries: 3182
7 Correct 48 ms 200 KB # of queries: 3184
8 Correct 44 ms 200 KB # of queries: 3074
9 Correct 59 ms 200 KB # of queries: 3156
10 Correct 35 ms 200 KB # of queries: 1852
11 Runtime error 0 ms 200 KB Execution killed with signal 13
12 Halted 0 ms 0 KB -

Subtask #2
0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 200 KB # of queries: 3030
2 Correct 54 ms 200 KB # of queries: 3022
3 Correct 59 ms 200 KB # of queries: 3180
4 Correct 47 ms 200 KB # of queries: 3174
5 Correct 59 ms 200 KB # of queries: 3176
6 Correct 51 ms 200 KB # of queries: 3182
7 Correct 48 ms 200 KB # of queries: 3184
8 Correct 44 ms 200 KB # of queries: 3074
9 Correct 59 ms 200 KB # of queries: 3156
10 Correct 35 ms 200 KB # of queries: 1852
11 Runtime error 0 ms 200 KB Execution killed with signal 13
12 Halted 0 ms 0 KB -