oj.uz

Submission #940843

# Submission time Handle Problem Language Result Execution time Memory
940843 2024-03-07T18:31:46 Z Doncho_Bonboncho Super Dango Maker (JOI22_dango3) C++17
100 / 100
 268 ms 936 KB 
#include "dango3.h"
#include <bits/stdc++.h>
   
using namespace std;


#ifndef LOCAL
#define cerr if(false)cerr
#endif

#define out(x) #x << " = " << x << "  "

int n;

void f( int currBr, std::vector< int > v ){

	cerr << endl << " ############ " << endl;
	cerr << out( currBr ) << endl;
	for( auto j : v ) cerr << j << " ";
	cerr << endl;

	if( currBr == 1 ){
		if( v.size() != n ) while( true );
		Answer( v );
		return;
	}

	int l = 0, r = v.size();

	while( l != r-1 ){

		std::vector< int > V;
		int m = ( l + r ) >> 1;
		for( int i=0 ; i <= m ; i++ ) V.push_back( v[i] );

		cerr << out( l ) << out( m ) << out( r ) << endl;
		for( auto j : V ) cerr << j << " ";
		cerr << endl;

		if( Query( V ) < currBr/2 ) l = m;
		else r = m;
	}

	cerr << out( r ) << endl;

	std::vector< int > firRet;
	std::vector< int > secRet;

	for( int i=0 ; i <= r ; i++ ) firRet.push_back( v[i] );
	for( int i=r+1 ; i < v.size() ; i++ ) secRet.push_back( v[i] );

	for( int i = r-2 ; i >= 0 ; i-- ){
		int currRem = firRet[i];
		std::swap( firRet[i], firRet[firRet.size() -1] );
		firRet.pop_back();

		if( Query( firRet ) != currBr/2 ){
			firRet.push_back( currRem );
			std::swap( firRet[i], firRet[firRet.size() -1] );
		}else secRet.push_back( currRem );
	}

	f( currBr /2, firRet );
	f( currBr /2 + ( currBr & 1 ), secRet );
}

void Solve(int N, int M) {
	
	n = N;

	std::vector< int > v;
	for( int i=1 ; i<=N*M ; i++ ) v.push_back( i );

	f( M, v );

}

Compilation message

dango3.cpp: In function 'void f(int, std::vector<int>)':
dango3.cpp:23:16: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   23 |   if( v.size() != n ) while( true );
      |       ~~~~~~~~~^~~~
dango3.cpp:50:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |  for( int i=r+1 ; i < v.size() ; i++ ) secRet.push_back( v[i] );
      |                   ~~^~~~~~~~~~

Subtask #1
2.0 / 2.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 3 ms 348 KB Output is correct
5 Correct 1 ms 440 KB Output is correct
6 Correct 2 ms 348 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 600 KB Output is correct
2 Correct 37 ms 604 KB Output is correct
3 Correct 72 ms 620 KB Output is correct
4 Correct 66 ms 632 KB Output is correct
5 Correct 22 ms 604 KB Output is correct
6 Correct 22 ms 656 KB Output is correct

Subtask #4
78.0 / 78.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 600 KB Output is correct
2 Correct 149 ms 768 KB Output is correct
3 Correct 250 ms 740 KB Output is correct
4 Correct 268 ms 936 KB Output is correct
5 Correct 84 ms 784 KB Output is correct
6 Correct 79 ms 780 KB Output is correct