Submission #311265

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

Anna

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

#define ll long long 

using namespace std ;

ll pot[38] ;

void Anna( int N, long long X, int K, int P[] )
{
	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(i,0);
			Set(i+1,0) ;
			continue ;
		}

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

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

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

			Set(i+1,0) ;

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

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

	}

}

Bruno

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

#define ll long long

using namespace std ;

ll pott[38] ;

long long Bruno( int N, int A[] )
{
  	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[i] == 0 && A[i+1] == 0)
		{
			ptr-- ;
			continue ;			
		}

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

	}

	return tot ;

}

• Subtask 1: 85 / 100