Submission #940843

#	Time	Username	Problem	Language	Result	Execution time	Memory
940843		Doncho_Bonboncho	Super Dango Maker (JOI22_dango3)	C++17	100 / 100	268 ms	936 KiB

dango3

#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 (stderr)

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 / 2
• Subtask 2: 5 / 5
• Subtask 3: 15 / 15
• Subtask 4: 78 / 78