oj.uz

Submission #446083

# Submission time Handle Problem Language Result Execution time Memory
446083 2021-07-20T19:00:42 Z raid Library (JOI18_library) C++17
100 / 100
 446 ms 320 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 );
  }
  if ( n == 1 ) {
    a[0] = 1;
    Answer( a );
    return;
  }
  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:48:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |   for ( int i = 1; i < pos.size(); ++i ) {
      |                    ~~^~~~~~~~~~~~

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 200 KB # of queries: 3030
2 Correct 45 ms 200 KB # of queries: 3022
3 Correct 51 ms 200 KB # of queries: 3180
4 Correct 52 ms 200 KB # of queries: 3174
5 Correct 53 ms 200 KB # of queries: 3176
6 Correct 48 ms 200 KB # of queries: 3182
7 Correct 37 ms 200 KB # of queries: 3184
8 Correct 50 ms 200 KB # of queries: 3074
9 Correct 52 ms 200 KB # of queries: 3156
10 Correct 28 ms 200 KB # of queries: 1852
11 Correct 0 ms 200 KB # of queries: 0
12 Correct 1 ms 200 KB # of queries: 4
13 Correct 1 ms 200 KB # of queries: 8
14 Correct 1 ms 200 KB # of queries: 18
15 Correct 2 ms 200 KB # of queries: 114
16 Correct 3 ms 200 KB # of queries: 262

Subtask #2
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 200 KB # of queries: 3030
2 Correct 45 ms 200 KB # of queries: 3022
3 Correct 51 ms 200 KB # of queries: 3180
4 Correct 52 ms 200 KB # of queries: 3174
5 Correct 53 ms 200 KB # of queries: 3176
6 Correct 48 ms 200 KB # of queries: 3182
7 Correct 37 ms 200 KB # of queries: 3184
8 Correct 50 ms 200 KB # of queries: 3074
9 Correct 52 ms 200 KB # of queries: 3156
10 Correct 28 ms 200 KB # of queries: 1852
11 Correct 0 ms 200 KB # of queries: 0
12 Correct 1 ms 200 KB # of queries: 4
13 Correct 1 ms 200 KB # of queries: 8
14 Correct 1 ms 200 KB # of queries: 18
15 Correct 2 ms 200 KB # of queries: 114
16 Correct 3 ms 200 KB # of queries: 262
17 Correct 360 ms 296 KB # of queries: 19966
18 Correct 443 ms 320 KB # of queries: 19762
19 Correct 359 ms 308 KB # of queries: 19970
20 Correct 314 ms 304 KB # of queries: 18814
21 Correct 312 ms 200 KB # of queries: 17848
22 Correct 423 ms 304 KB # of queries: 19974
23 Correct 446 ms 312 KB # of queries: 19954
24 Correct 146 ms 320 KB # of queries: 9848
25 Correct 389 ms 300 KB # of queries: 19562
26 Correct 384 ms 292 KB # of queries: 18446
27 Correct 120 ms 200 KB # of queries: 9180
28 Correct 362 ms 200 KB # of queries: 19976
29 Correct 320 ms 200 KB # of queries: 17964
30 Correct 417 ms 312 KB # of queries: 19976