oj.uz

Submission #410007

# Submission time Handle Problem Language Result Execution time Memory
410007 2021-05-21T21:03:06 Z CaroLinda The Collection Game (BOI21_swaps) C++14
35 / 100
 39 ms 404 KB 
//
// --- 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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Correct 3 ms 200 KB Correct
3 Correct 12 ms 200 KB Correct
4 Correct 29 ms 340 KB Correct
5 Correct 29 ms 340 KB Correct
6 Correct 39 ms 340 KB Correct
7 Correct 30 ms 348 KB Correct
8 Correct 31 ms 344 KB Correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Correct 4 ms 200 KB Correct
3 Correct 11 ms 320 KB Correct
4 Correct 29 ms 340 KB Correct
5 Correct 28 ms 340 KB Correct
6 Correct 30 ms 380 KB Correct
7 Correct 35 ms 356 KB Correct
8 Correct 26 ms 340 KB Correct
9 Correct 28 ms 344 KB Correct
10 Correct 31 ms 344 KB Correct
11 Correct 29 ms 344 KB Correct
12 Correct 29 ms 344 KB Correct
13 Correct 28 ms 344 KB Correct

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Correct 4 ms 200 KB Correct

Subtask #4
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Correct 4 ms 200 KB Correct
3 Correct 1 ms 200 KB Correct
4 Correct 4 ms 200 KB Correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Correct 3 ms 200 KB Correct
3 Correct 11 ms 200 KB Correct
4 Correct 37 ms 348 KB Correct

Subtask #6
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Correct 3 ms 200 KB Correct
3 Correct 11 ms 200 KB Correct
4 Correct 37 ms 348 KB Correct
5 Correct 1 ms 200 KB Correct
6 Correct 3 ms 200 KB Correct
7 Correct 10 ms 200 KB Correct
8 Correct 31 ms 344 KB Correct
9 Correct 30 ms 340 KB Correct
10 Correct 34 ms 340 KB Correct
11 Correct 31 ms 344 KB Correct
12 Correct 37 ms 404 KB Correct
13 Correct 1 ms 200 KB Correct
14 Correct 4 ms 200 KB Correct
15 Correct 11 ms 200 KB Correct
16 Correct 33 ms 348 KB Correct

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Correct 4 ms 200 KB Correct
3 Correct 11 ms 200 KB Correct
4 Correct 28 ms 376 KB Correct
5 Runtime error 28 ms 340 KB Execution killed with signal 13

Subtask #8
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Correct 4 ms 200 KB Correct
3 Correct 11 ms 200 KB Correct
4 Correct 28 ms 376 KB Correct
5 Runtime error 28 ms 340 KB Execution killed with signal 13

Subtask #9
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Correct 4 ms 200 KB Correct
3 Correct 9 ms 200 KB Correct
4 Correct 29 ms 340 KB Correct
5 Runtime error 36 ms 344 KB Execution killed with signal 13
6 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Correct 4 ms 200 KB Correct
3 Correct 9 ms 200 KB Correct
4 Correct 29 ms 340 KB Correct
5 Runtime error 36 ms 344 KB Execution killed with signal 13
6 Halted 0 ms 0 KB -

Subtask #11
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Correct 4 ms 200 KB Correct
3 Correct 10 ms 312 KB Correct
4 Correct 29 ms 340 KB Correct
5 Runtime error 36 ms 340 KB Execution killed with signal 13
6 Halted 0 ms 0 KB -

Subtask #12
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Correct 4 ms 200 KB Correct
3 Correct 10 ms 312 KB Correct
4 Correct 29 ms 340 KB Correct
5 Runtime error 36 ms 340 KB Execution killed with signal 13
6 Halted 0 ms 0 KB -