Submission #410007

#	Time	Username	Problem	Language	Result	Execution time	Memory
410007		CaroLinda	The Collection Game (BOI21_swaps)	C++14	35 / 100	39 ms	404 KiB

swaps

//
// --- Sample implementation for the task swaps ---
//
// To compile this program with the sample grader, place:
//     swaps.h swaps_sample.cpp sample_grader.cpp
// in a single folder and run:
//     g++ swaps_sample.cpp sample_grader.cpp
// in this folder.
//
#include "swaps.h"
#include <bits/stdc++.h>

#define sz(x) (int)(x.size())
#define all(x) x.begin(),x.end()

using namespace std ;

vector<int> r ;

void solve(int N, int V) 
{
	vector< vector<int> > space ;
	for(int i = 1 ; i <= N ; i++ ) space.push_back({i}) ;

	while( sz(space) > 1 )
	{
		/*for(auto e : space )
		{
			for(auto ee : e ) cout <<ee <<" " ;
			cout << endl ;
		}*/
		vector< vector<int> > aux ;

		sort(all(space), [&](vector<int> a, vector<int> b) { return sz(a) > sz(b) ; }) ;

		int p = sz(space[0]) ;

		for(int i = 0 ; i+1 < sz(space) ; i += 2 ) 
			aux.push_back(vector<int>(sz(space[i])+sz(space[i+1]) , 0)) ;
		if( sz(space)&1 ) aux.push_back( space.back() ) ;

		while(p--)
		{
			for(int i = 0 ; i+1 < sz(space) ; i += 2 )
				for(int j = 0 ; j < sz(space[i+1]) ; j++ ) 
					schedule( space[i][j] , space[i+1][j] ) ;

			r = visit() ;
			int id = 0 ;

			for(int i = 0 ; i+1 < sz(space) ; i += 2 )
			{

				for(int j = 0 ; j < sz(space[i+1]) ; j++ )
					if(!r[id++]) swap( space[i][j] , space[i+1][j] ) ;

				int t1 = sz(space[i]) , t2 = sz(space[i+1]) ;

				for(int j = 0 ; j < sz(aux[i>>1]) ; j++ )
					if( aux[i>>1][j] == 0 )
					{
						aux[i>>1][j] = space[i][0] ;
						break ;
					}
				space[i].erase( space[i].begin() , space[i].begin()+1 ) ;

				if(t1 == t2) 
				{
					for(int j = sz(aux[i>>1])-1 ; j >= 0 ; j-- )
						if(aux[i>>1][j] == 0)
						{
							aux[i>>1][j] = space[i+1].back() ;
							break ;
						}
					space[i+1].erase( space[i+1].begin()+t2-1 , space[i+1].end() ) ;
				}

			}

		}

		swap(aux, space) ;

	}

	answer(space[0]) ;
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 3 / 3
• Subtask 4: 2 / 2
• Subtask 5: 9 / 9
• Subtask 6: 6 / 6
• Subtask 7: 0 / 9
• Subtask 8: 0 / 6
• Subtask 9: 0 / 21
• Subtask 10: 0 / 14
• Subtask 11: 0 / 9
• Subtask 12: 0 / 6