oj.uz

Submission #231107

# Submission time Handle Problem Language Result Execution time Memory
231107 2020-05-12T18:05:37 Z CaroLinda Last supper (IOI12_supper) C++14
100 / 100
 161 ms 19696 KB 
#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] ) ;

}

#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 5376 KB Output is correct
2 Correct 10 ms 5376 KB Output is correct
3 Correct 12 ms 5632 KB Output is correct
4 Correct 12 ms 5632 KB Output is correct
5 Correct 15 ms 5800 KB Output is correct
6 Correct 15 ms 5888 KB Output is correct
7 Correct 16 ms 5888 KB Output is correct
8 Correct 15 ms 6144 KB Output is correct
9 Correct 15 ms 5888 KB Output is correct
10 Correct 15 ms 6144 KB Output is correct
11 Correct 15 ms 5888 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 6400 KB Output is correct
2 Correct 63 ms 9728 KB Output is correct
3 Correct 136 ms 19696 KB Output is correct
4 Correct 104 ms 15088 KB Output is correct
5 Correct 104 ms 15088 KB Output is correct
6 Correct 124 ms 15600 KB Output is correct
7 Correct 135 ms 16880 KB Output is correct
8 Correct 105 ms 17904 KB Output is correct
9 Correct 90 ms 12368 KB Output is correct
10 Correct 161 ms 18160 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 14208 KB Output is correct
2 Correct 135 ms 16368 KB Output is correct
3 Correct 143 ms 16368 KB Output is correct
4 Correct 137 ms 16016 KB Output is correct
5 Correct 130 ms 14576 KB Output is correct
6 Correct 148 ms 17904 KB Output is correct
7 Correct 136 ms 17392 KB Output is correct
8 Correct 118 ms 19696 KB Output is correct
9 Correct 124 ms 15600 KB Output is correct
10 Correct 136 ms 17648 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 5888 KB Output is correct
2 Correct 15 ms 6144 KB Output is correct
3 Correct 15 ms 5632 KB Output is correct
4 Correct 15 ms 5888 KB Output is correct
5 Correct 16 ms 5888 KB Output is correct
6 Correct 14 ms 5888 KB Output is correct
7 Correct 15 ms 5888 KB Output is correct
8 Correct 16 ms 5888 KB Output is correct
9 Correct 16 ms 5888 KB Output is correct
10 Correct 18 ms 6144 KB Output is correct

Subtask #5
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 15856 KB Output is correct - 120000 bits used
2 Correct 150 ms 16472 KB Output is correct - 122000 bits used
3 Correct 136 ms 16368 KB Output is correct - 125000 bits used
4 Correct 141 ms 16368 KB Output is correct - 125000 bits used
5 Correct 137 ms 16368 KB Output is correct - 125000 bits used
6 Correct 145 ms 16368 KB Output is correct - 125000 bits used
7 Correct 143 ms 16368 KB Output is correct - 124828 bits used
8 Correct 136 ms 16368 KB Output is correct - 124910 bits used
9 Correct 143 ms 16368 KB Output is correct - 125000 bits used
10 Correct 118 ms 18672 KB Output is correct - 125000 bits used