Submission #231107

#	Time	Username	Problem	Language	Result	Execution time	Memory
231107		CaroLinda	Last supper (IOI12_supper)	C++14	100 / 100	161 ms	19696 KiB

advisor

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

#define lp(i,a,b) for(int i = a ; i < b ; i++)
#define pii pair<int,int>
#define pb push_back
#define mk make_pair
#define ff first
#define ss second

const int MAXN = 1e5+10 ;
const int inf = 1e9+10 ;

using namespace std ;

bool is_active[MAXN*2] , scaffold[MAXN] ;
vector<int> cores[MAXN] ;
int ptr[MAXN] , active[MAXN] ;
set<pii> s ;

int get_next(int cor)
{
	if( ptr[cor] >= (int)cores[cor].size() ) return inf ;
	return cores[cor][ ptr[cor]++ ] ;
}

void ComputeAdvice(int *C, int N, int K, int M) 
{


	lp(i,0,N) cores[ C[i] ].pb( i ) ;
	lp(i,0,K) s.insert( mk( get_next(i) , i ) ) , scaffold[i] = true , active[i] = N+i ;

	for(int i = 0 ; i < N ; i++ )
	{
		active[ C[i] ] = i ;

		if( scaffold[ C[i] ] )
		{

			s.erase( s.find( mk( i , C[i] ) ) ) ;
			s.insert( mk( get_next(C[i]) , C[i] ) ) ;

			continue ;
		}

		auto par = *prev(s.end()) ;
		s.erase( prev( s.end() ) ) ;

		scaffold[ par.ss ] = false ;
		scaffold[ C[i] ] = true ;

		is_active[ active[par.ss] ] = true ;

		int x = get_next( C[i] ) ;
		if( x <= i ) x = get_next(C[i]) ;

		s.insert( mk( x , C[i] ) ) ;

	}

	lp(i,0,K) WriteAdvice( is_active[N+i]  ) ;
	lp(i,0,N) WriteAdvice( is_active[i] ) ;

}

assistant

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

#define lp(i,a,b) for(int i = a ; i < b ; i++)
#define pii pair<int,int>
#define pb push_back
#define mk make_pair
#define ff first
#define ss second

const int MAXN = 1e5+10 ;

using namespace std ;	

set<int> actives ;
bool scaff[MAXN] ;

void Assist(unsigned char *A, int N, int K, int R)
{

	int idx = -1 ;

	lp(i,0,K) 
	{
		scaff[i] = true ;
		if( A[++idx] ) actives.insert(i) ;
	}

	lp(i,0,N)
	{
		int x = GetRequest() ;
		if( scaff[x] ) 
		{
			if( A[++idx] ) actives.insert( x ) ;
			continue ;
		}

		scaff[x] = true ;

		int toErase = *actives.begin() ;
		actives.erase( actives.begin() ) ;

		scaff[ toErase ] = false ;

		PutBack(toErase) ;

		if( A[++idx] ) actives.insert(x) ;

	}
}

• Subtask 1: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 35 / 35
• Subtask 5: 39 / 39