oj.uz

Submission #116759

# Submission time Handle Problem Language Result Execution time Memory
116759 2019-06-13T17:35:04 Z faustaadp Last supper (IOI12_supper) C++17
34 / 100
 337 ms 31420 KB 
#include "advisor.h"
#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
ll a[101010];
ll w[101010];
ll ada[101010];
ll las[101010];
ll lok[101010];
ll loki[101010];
ll y[101010];
void ComputeAdvice(int *C, int N, int K, int M) 
{
	priority_queue<pair<ll,ll> > pq;
	ll i,j;
	ll x=ceil(log(K+1)/log(2));
	for(i=0;i<N;i++)
		a[i]=C[i];
	for(i=0;i<N;i++)
  	{
  	//	cout<<i<<" "<<isi[i]<<"\n";
  		las[i]=N;
  	}
  	for(i=N-1;i>=0;i--)
  	{
  		y[i]=las[a[i]];
  		las[a[i]]=i;
  	}
  	for(i=0;i<K;i++)
  	{
  		pq.push(mp(las[i],i));
  		ada[i]=1;
  		lok[i]=i;
  		loki[i]=i;
  	}
	for (i = 0; i < N; i++) 
  	{
	    int req = a[i];
  		if(ada[req])
  		{
  			w[i]=K;
  			las[a[i]]=y[i];
	  		pq.push(mp(las[a[i]],a[i]));
  		}
  		else
  		{
	  		while(!pq.empty()&&ada[pq.top().se]==0)pq.pop();
	  		while(!pq.empty()&&las[pq.top().se]!=pq.top().fi)pq.pop();
	  		ada[req]=1;
	  		ll tem=pq.top().se;
	  		ll za=loki[tem];
	  		lok[za]=req;
	  		loki[req]=za;
	  		w[i]=za;
	//  		cout<<i<<" "<<tem<<" "<<za<<"_)	\n";
	  //		cout<<lok[0]<<"   "<<lok[1]<<"\n";
	  		pq.pop();
	  		ada[tem]=0;
	  		las[a[i]]=y[i];
	  		pq.push(mp(las[a[i]],a[i]));
  		}
  	}
	for(i=0;i<N;i++)
	{
		for(j=0;j<x;j++)
			if(w[i]&(1<<j))
			{
			//	cout<<"_1\n";
				WriteAdvice(1);
			}
			else
			{
			//	cout<<"_0\n";
				WriteAdvice(0);
			}
	}
}

#include "assistant.h"
#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
ll z[2010101],isi[101010];
ll loka[101010];
void Assist(unsigned char *A, int N, int K, int R) 
{
	ll i,j;
	ll x=ceil(log(K+1)/log(2));
  	for (i = 0; i < R; i++)
  	{
  		if(A[i])
  		{
  			z[i]=1;
  		}
  		//cout<<i<<"___"<<A[i]<<"\n";
  		//z[(ll)A[i]]=1; 
  	}
  	for (i = 0; i < N; i++) 
  		for(j=0;j<x;j++)
  			isi[i]+=z[i*x+j]*(1<<j);
  	//for (i = 0; i < N; i++)
  //		cout<<i<<" "<<isi[i]<<"\n"; 
  	for (i = 0; i < K; i++)
  		loka[i]=i; 
  	for (i = 0; i < N; i++) 
  	{
	    int req = GetRequest();
  		if(isi[i]==K)
  		{
  		}
  		else
  		{
	  		ll za=isi[i];
	  		PutBack(loka[za]);
	  		loka[za]=req;
  		}
  	}
 
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 896 KB Output is correct
2 Correct 5 ms 904 KB Output is correct
3 Correct 6 ms 1180 KB Output is correct
4 Correct 7 ms 1332 KB Output is correct
5 Correct 7 ms 1280 KB Output is correct
6 Correct 12 ms 1648 KB Output is correct
7 Correct 15 ms 1972 KB Output is correct
8 Correct 15 ms 2028 KB Output is correct
9 Correct 14 ms 1976 KB Output is correct
10 Correct 16 ms 2164 KB Output is correct
11 Correct 16 ms 2112 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 3280 KB Output is correct
2 Correct 129 ms 13308 KB Output is correct
3 Correct 317 ms 31420 KB Output is correct
4 Correct 152 ms 16924 KB Output is correct
5 Correct 221 ms 22336 KB Output is correct
6 Correct 276 ms 26644 KB Output is correct
7 Correct 309 ms 29516 KB Output is correct
8 Correct 242 ms 25444 KB Output is correct
9 Correct 114 ms 14672 KB Output is correct
10 Correct 337 ms 29932 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 252 ms 24128 KB Output is correct
2 Correct 327 ms 29552 KB Output is correct
3 Correct 323 ms 30504 KB Output is correct
4 Correct 296 ms 30696 KB Output is correct
5 Correct 285 ms 30200 KB Output is correct
6 Correct 293 ms 30624 KB Output is correct
7 Correct 297 ms 30684 KB Output is correct
8 Correct 295 ms 30664 KB Output is correct
9 Correct 294 ms 30532 KB Output is correct
10 Correct 302 ms 30612 KB Output is correct

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 1280 KB Error - advice is too long
2 Halted 0 ms 0 KB -

Subtask #5
8.0 / 39.0

# Verdict Execution time Memory Grader output
1 Partially correct 295 ms 29732 KB Output is partially correct - 1500000 bits used
2 Partially correct 295 ms 29512 KB Output is partially correct - 1500000 bits used
3 Partially correct 310 ms 29820 KB Output is partially correct - 1500000 bits used
4 Partially correct 302 ms 29780 KB Output is partially correct - 1500000 bits used
5 Partially correct 296 ms 29648 KB Output is partially correct - 1500000 bits used
6 Partially correct 300 ms 29724 KB Output is partially correct - 1500000 bits used
7 Partially correct 308 ms 29568 KB Output is partially correct - 1497585 bits used
8 Partially correct 315 ms 29924 KB Output is partially correct - 1500000 bits used
9 Partially correct 300 ms 29716 KB Output is partially correct - 1500000 bits used
10 Partially correct 312 ms 29784 KB Output is partially correct - 1500000 bits used