oj.uz

Submission #311272

# Submission time Handle Problem Language Result Execution time Memory
311272 2020-10-09T19:52:35 Z CaroLinda Broken Device (JOI17_broken_device) C++14
100 / 100
 60 ms 3328 KB 
#include "Annalib.h"
#include <bits/stdc++.h>

#define ll long long 
#define all(x) x.begin(),x.end()

using namespace std ;

ll pot[38] ;

void Anna( int N, long long X, int K, int P[] )
{
	srand(36) ;

	vector<int> vec(N,0) ;
	iota(all(vec),0) ;
	random_shuffle(all(vec)) ;

	pot[0] = 1LL ;
	for(int i = 1 ; i <= 37 ; i++ )
		pot[i] = pot[i-1]*3LL ;

	vector<bool> isBroken(N, false ) ;
	for(int i = 0 ; i <  K ; i++ ) isBroken[ P[i] ] = true ;

	vector<int> base3( 38, 0 ) ;
	for(int i = 37 ; i >= 0 ; i-- )
	{
		base3[i] = X/pot[i] ;
		X -= pot[i] * base3[i] ;
	}

	//01 = 0
	//10 = 1
	//11 = 2

	for(int i = 0, ptr = 0 ; i+1 < N ; i += 2 , ptr++ )
	{

		if( ptr > 37 )
		{
			Set(vec[i],0);
			Set( vec[i+1] ,0) ;
			continue ;
		}

		if(isBroken[ vec[i] ] && isBroken[ vec[i+1] ]) 
		{
			Set( vec[i] ,0) ;
			Set( vec[i+1] ,0) ;
			ptr-- ;
			continue ;
		}

		if(isBroken[ vec[i] ])
		{
			Set(vec[i],0) ;

			if( base3[ptr] == 0 )
				Set(vec[i+1], 1) ;
			else 
			{
				ptr-- ;
				Set(vec[i+1],0) ;
			}
		}
		else if( isBroken[ vec[i+1] ] )
		{

			Set(vec[i+1],0) ;

			if( base3[ptr] == 1 )
				Set(vec[i],1) ;
			else 
			{
				ptr-- ;
				Set(vec[i],0) ;
			}

		}
		else
		{
			if( base3[ptr] == 0 )
			{
				Set(vec[i],0) ;
				Set(vec[i+1],1) ;
			}
			else if(base3[ptr] == 1)
			{
				Set( vec[i] ,1) ;
				Set( vec[i+1] ,0) ;
			}
			else 
			{
				Set( vec[i] ,1) ;
				Set( vec[i+1] ,1) ;
			}
		}

	}

}

#include "Brunolib.h"
#include <bits/stdc++.h>

#define all(x) x.begin(),x.end()
#define ll long long

using namespace std ;

ll pott[38] ;

long long Bruno( int N, int A[] )
{
	srand(36) ;

	vector<int> vec(N,0) ;
	iota(all(vec),0) ;
	random_shuffle(all(vec)) ;

  	pott[0] = 1LL ;
	for(int i = 1 ; i <= 37 ; i++ )
		pott[i] = pott[i-1]*3LL ;

	ll tot = 0LL ;

	for(int i = 0, ptr = 0 ; i+1 < N && ptr <= 37 ; i += 2 , ptr++ )
	{

		if( A[ vec[i] ] == 0 && A[ vec[i+1] ] == 0)
		{
			ptr-- ;
			continue ;			
		}

		if( A[ vec[i] ] == 1 && A[ vec[i+1] ] == 0 )
			tot += pott[ptr] ;
		else if( A[ vec[i] ] == 1 && A[ vec[i+1] ] == 1 )
			tot += 2LL*pott[ptr] ;

	}

	return tot ;

}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 3056 KB Output is correct - L* = 40
2 Correct 55 ms 3056 KB Output is correct - L* = 40
3 Correct 54 ms 2800 KB Output is correct - L* = 40
4 Correct 55 ms 3072 KB Output is correct - L* = 40
5 Correct 55 ms 3072 KB Output is correct - L* = 40
6 Correct 60 ms 3072 KB Output is correct - L* = 40
7 Correct 55 ms 3312 KB Output is correct - L* = 40
8 Correct 55 ms 3056 KB Output is correct - L* = 40
9 Correct 54 ms 3072 KB Output is correct - L* = 40
10 Correct 56 ms 3056 KB Output is correct - L* = 40
11 Correct 57 ms 3056 KB Output is correct - L* = 40
12 Correct 54 ms 3056 KB Output is correct - L* = 40
13 Correct 56 ms 3064 KB Output is correct - L* = 40
14 Correct 55 ms 3056 KB Output is correct - L* = 40
15 Correct 55 ms 3072 KB Output is correct - L* = 40
16 Correct 55 ms 3056 KB Output is correct - L* = 40
17 Correct 54 ms 3072 KB Output is correct - L* = 40
18 Correct 55 ms 3072 KB Output is correct - L* = 40
19 Correct 56 ms 3072 KB Output is correct - L* = 40
20 Correct 55 ms 3072 KB Output is correct - L* = 40
21 Correct 55 ms 3056 KB Output is correct - L* = 40
22 Correct 55 ms 3072 KB Output is correct - L* = 40
23 Correct 55 ms 3072 KB Output is correct - L* = 40
24 Correct 54 ms 3056 KB Output is correct - L* = 40
25 Correct 58 ms 3328 KB Output is correct - L* = 40
26 Correct 54 ms 3056 KB Output is correct - L* = 40
27 Correct 55 ms 3064 KB Output is correct - L* = 40
28 Correct 55 ms 3064 KB Output is correct - L* = 40
29 Correct 54 ms 3056 KB Output is correct - L* = 40
30 Correct 55 ms 3072 KB Output is correct - L* = 40
31 Correct 54 ms 3056 KB Output is correct - L* = 40
32 Correct 57 ms 3072 KB Output is correct - L* = 40
33 Correct 55 ms 3056 KB Output is correct - L* = 40
34 Correct 55 ms 3056 KB Output is correct - L* = 40
35 Correct 54 ms 3064 KB Output is correct - L* = 40
36 Correct 55 ms 2800 KB Output is correct - L* = 40
37 Correct 55 ms 3072 KB Output is correct - L* = 40
38 Correct 55 ms 3072 KB Output is correct - L* = 40
39 Correct 55 ms 3064 KB Output is correct - L* = 40
40 Correct 55 ms 3056 KB Output is correct - L* = 40