Submission #311272

#	Time	Username	Problem	Language	Result	Execution time	Memory
311272		CaroLinda	Broken Device (JOI17_broken_device)	C++14	100 / 100	60 ms	3328 KiB

Anna

#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) ;
			}
		}

	}

}

Bruno

#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 / 100