oj.uz

Submission #478524

# Submission time Handle Problem Language Result Execution time Memory
478524 2021-10-07T23:01:56 Z CaroLinda The Collection Game (BOI21_swaps) C++14
100 / 100
 9 ms 384 KB 
#include "swaps.h"
#include <bits/stdc++.h>

#define sz(x) (int)(x.size() )
#define debug 

const int MAX = 515 ;

using namespace std ;

int n , N ;
int arr[MAX] ;
vector< pair<int,int> > pairs ;
vector<int> _visit ;

void make_schedule(int i, int j )
{
	_visit.push_back(-1) ;
	pairs.push_back(make_pair(i,j) ) ;
	i = arr[i] , j = arr[j] ;

	if( i >= n || j >= n )
	{
		_visit.back() = (i > j )  ;
		return ;
	}	

	schedule(i+1,j+1) ;
}

void make_visit()
{
	vector<int> v = visit() ;

	for(int i = 0 , ptr = 0 ; i < sz(_visit) ; i++ )
	{
		if( _visit[i] == -1 ) _visit[i] = v[ptr++] ;
		if( _visit[i] ) swap( arr[ pairs[i].first ] , arr[ pairs[i].second ] ) ;
	}

	_visit.clear() ;
	pairs.clear() ;
}

void solve(int _n, int V) 
{

	n = _n ;
	int k = 0 ;
	while( (1<<k) < n ) k++ ;
	N = (1<<k) ;

	iota(arr, arr+N , 0 ) ;

	for(int i = 1 ; i <= k ; i++ )
	{

		for(int j = i-1 , p = (1<<j) ; j >= 0 ; j-- , p >>= 1)
		{
			for(int g = 0 ; g < N ; g++ )
			{
				int num = g/p ;
				if( (num&1) == 1 ) continue ;

				int dist = g-num*p ;
				int op = (num+2)*p - dist - 1 ;

				if(j < i-1 ) op = g+p ;

				make_schedule( g , op ) ;
			}
			make_visit() ;
		}

	}

	vector<int> r ;
	for(int i = n-1 ; i >= 0 ; i-- ) r.push_back(arr[i]+1 ) ;

	answer(r) ;

}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Correct 1 ms 200 KB Correct
3 Correct 2 ms 296 KB Correct
4 Correct 9 ms 300 KB Correct
5 Correct 6 ms 304 KB Correct
6 Correct 6 ms 304 KB Correct
7 Correct 7 ms 300 KB Correct
8 Correct 5 ms 304 KB Correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 200 KB Correct
2 Correct 1 ms 296 KB Correct
3 Correct 2 ms 200 KB Correct
4 Correct 5 ms 304 KB Correct
5 Correct 6 ms 300 KB Correct
6 Correct 5 ms 300 KB Correct
7 Correct 5 ms 304 KB Correct
8 Correct 5 ms 300 KB Correct
9 Correct 5 ms 308 KB Correct
10 Correct 5 ms 304 KB Correct
11 Correct 5 ms 300 KB Correct
12 Correct 5 ms 308 KB Correct
13 Correct 5 ms 308 KB Correct

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Correct 1 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 1 ms 200 KB Correct
3 Correct 0 ms 200 KB Correct
4 Correct 1 ms 200 KB Correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Correct
2 Correct 1 ms 296 KB Correct
3 Correct 3 ms 200 KB Correct
4 Correct 5 ms 304 KB Correct

Subtask #6
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Correct
2 Correct 1 ms 296 KB Correct
3 Correct 3 ms 200 KB Correct
4 Correct 5 ms 304 KB Correct
5 Correct 1 ms 200 KB Correct
6 Correct 1 ms 200 KB Correct
7 Correct 2 ms 200 KB Correct
8 Correct 7 ms 304 KB Correct
9 Correct 7 ms 300 KB Correct
10 Correct 5 ms 308 KB Correct
11 Correct 5 ms 304 KB Correct
12 Correct 7 ms 304 KB Correct
13 Correct 1 ms 200 KB Correct
14 Correct 2 ms 200 KB Correct
15 Correct 3 ms 300 KB Correct
16 Correct 6 ms 296 KB Correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Correct 1 ms 296 KB Correct
3 Correct 2 ms 200 KB Correct
4 Correct 5 ms 304 KB Correct
5 Correct 5 ms 280 KB Correct

Subtask #8
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Correct 1 ms 296 KB Correct
3 Correct 2 ms 200 KB Correct
4 Correct 5 ms 304 KB Correct
5 Correct 5 ms 280 KB Correct
6 Correct 1 ms 200 KB Correct
7 Correct 1 ms 200 KB Correct
8 Correct 3 ms 248 KB Correct
9 Correct 5 ms 300 KB Correct
10 Correct 7 ms 304 KB Correct
11 Correct 5 ms 304 KB Correct
12 Correct 5 ms 300 KB Correct
13 Correct 6 ms 308 KB Correct
14 Correct 5 ms 304 KB Correct
15 Correct 6 ms 308 KB Correct
16 Correct 5 ms 308 KB Correct
17 Correct 5 ms 304 KB Correct
18 Correct 5 ms 304 KB Correct
19 Correct 1 ms 200 KB Correct
20 Correct 1 ms 200 KB Correct
21 Correct 2 ms 304 KB Correct
22 Correct 5 ms 308 KB Correct
23 Correct 7 ms 304 KB Correct

Subtask #9
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Correct 1 ms 200 KB Correct
3 Correct 2 ms 200 KB Correct
4 Correct 5 ms 304 KB Correct
5 Correct 5 ms 288 KB Correct
6 Correct 5 ms 284 KB Correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Correct 1 ms 200 KB Correct
3 Correct 2 ms 200 KB Correct
4 Correct 5 ms 304 KB Correct
5 Correct 5 ms 288 KB Correct
6 Correct 5 ms 284 KB Correct
7 Correct 0 ms 200 KB Correct
8 Correct 1 ms 200 KB Correct
9 Correct 2 ms 300 KB Correct
10 Correct 5 ms 304 KB Correct
11 Correct 5 ms 304 KB Correct
12 Correct 5 ms 304 KB Correct
13 Correct 7 ms 300 KB Correct
14 Correct 5 ms 300 KB Correct
15 Correct 5 ms 300 KB Correct
16 Correct 6 ms 304 KB Correct
17 Correct 5 ms 304 KB Correct
18 Correct 7 ms 300 KB Correct
19 Correct 5 ms 304 KB Correct
20 Correct 1 ms 200 KB Correct
21 Correct 2 ms 200 KB Correct
22 Correct 2 ms 200 KB Correct
23 Correct 5 ms 304 KB Correct
24 Correct 5 ms 280 KB Correct
25 Correct 5 ms 280 KB Correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Correct 2 ms 200 KB Correct
3 Correct 3 ms 200 KB Correct
4 Correct 5 ms 300 KB Correct
5 Correct 4 ms 304 KB Correct
6 Correct 5 ms 280 KB Correct
7 Correct 7 ms 284 KB Correct

Subtask #12
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Correct 2 ms 200 KB Correct
3 Correct 3 ms 200 KB Correct
4 Correct 5 ms 300 KB Correct
5 Correct 4 ms 304 KB Correct
6 Correct 5 ms 280 KB Correct
7 Correct 7 ms 284 KB Correct
8 Correct 0 ms 200 KB Correct
9 Correct 1 ms 200 KB Correct
10 Correct 1 ms 200 KB Correct
11 Correct 2 ms 200 KB Correct
12 Correct 5 ms 300 KB Correct
13 Correct 5 ms 304 KB Correct
14 Correct 5 ms 304 KB Correct
15 Correct 5 ms 300 KB Correct
16 Correct 5 ms 304 KB Correct
17 Correct 5 ms 308 KB Correct
18 Correct 7 ms 304 KB Correct
19 Correct 7 ms 304 KB Correct
20 Correct 5 ms 304 KB Correct
21 Correct 5 ms 300 KB Correct
22 Correct 1 ms 200 KB Correct
23 Correct 1 ms 200 KB Correct
24 Correct 2 ms 304 KB Correct
25 Correct 6 ms 304 KB Correct
26 Correct 5 ms 300 KB Correct
27 Correct 5 ms 384 KB Correct
28 Correct 7 ms 284 KB Correct