oj.uz

Submission #698776

# Submission time Handle Problem Language Result Execution time Memory
698776 2023-02-14T09:42:27 Z PedroBigMan Last supper (IOI12_supper) C++14
100 / 100
 153 ms 15352 KB 
/*
Author of all code: Pedro BIGMAN Dias
Last edit: 15/02/2021
*/
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <deque>
#include <list>
#include <iomanip>
#include <stdlib.h>
#include <time.h>
#include <cstring>
#include "advisor.h"
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
#define REP(i,a,b) for(ll i=(ll) a; i<(ll) b; i++)
#define pb push_back
#define mp make_pair
#define pl pair<ll,ll>
#define ff first
#define ss second
#define whole(x) x.begin(),x.end()
#define DEBUG(i) cout<<"Pedro"<<i<<endl
#define INF 1000000000000000000LL
#define EPS ((ld)0.00000000001)
#define pi ((ld)3.141592653589793)
#define VV(vvvv,NNNN,xxxx); REP(iiiii,0,NNNN) {vvvv.pb(xxxx);}

template<class A> 
void Out(vector<A> a) {REP(i,0,a.size()) {cout<<a[i]<<" ";} cout<<endl;}

template<class A>
void In(vector<A> &a, ll N) {A cur; REP(i,0,N) {cin>>cur; a.pb(cur);}} 

void ComputeAdvice(int *CC, int N, int K, int M) 
{
	vector<ll> C; REP(i,0,N) {C.pb(*(CC+i));}
	vector<ll> nxt(N,N); REP(i,0,N) {nxt[C[i]]=min(nxt[C[i]],i);}
	set<pl> s; REP(i,0,K) {s.insert(mp(nxt[i],i));}
	vector<bool> rest(N,false);
	vector<vector<ll> > pos(N,vector<ll>(0));
	REP(i,0,N) {pos[C[i]].pb(i);}
	REP(i,0,N) {pos[i].pb(N);}
	set<pl>::iterator it,it2; ll cur;
	REP(i,0,N)
	{
		cur=C[i];
		it=s.lower_bound(mp(nxt[cur],cur));
		if(it!=s.end() && it->ss==cur)
		{
			rest[i]=true; nxt[cur]=*upper_bound(whole(pos[cur]),i);
			s.erase(it); s.insert(mp(nxt[cur],cur));
		}
		else
		{
			it2=s.end(); it2--; s.erase(it2);
			nxt[cur]=*upper_bound(whole(pos[cur]),i);
			s.insert(mp(nxt[cur],cur));
		}
	}
	ll ind;
	REP(i,0,K)
	{
		ind=pos[i][0]; if(ind==N || !rest[ind]) {WriteAdvice(0);} else {WriteAdvice(1);}
	}
	REP(i,0,N)
	{
		cur=C[i];
		ind=*upper_bound(whole(pos[cur]),i);
		if(ind==N || !rest[ind]) {WriteAdvice(0);} else {WriteAdvice(1);}
	}
}

/*
Author of all code: Pedro BIGMAN Dias
Last edit: 15/02/2021
*/
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <deque>
#include <list>
#include <iomanip>
#include <stdlib.h>
#include <time.h>
#include <cstring>
#include "assistant.h"
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
#define REP(i,a,b) for(ll i=(ll) a; i<(ll) b; i++)
#define pb push_back
#define mp make_pair
#define pl pair<ll,ll>
#define ff first
#define ss second
#define whole(x) x.begin(),x.end()
#define DEBUG(i) cout<<"Pedro"<<i<<endl
#define INF 1000000000000000000LL
#define EPS ((ld)0.00000000001)
#define pi ((ld)3.141592653589793)
#define VV(vvvv,NNNN,xxxx); REP(iiiii,0,NNNN) {vvvv.pb(xxxx);}
ll mod=1000000007LL;

template<class A> 
void Out(vector<A> a) {REP(i,0,a.size()) {cout<<a[i]<<" ";} cout<<endl;}

template<class A>
void In(vector<A> &a, ll N) {A cur; REP(i,0,N) {cin>>cur; a.pb(cur);}} 

void Assist(unsigned char *AA, int N, int K, int R) 
{ 
	vector<bool> A(K+N,false); REP(i,0,K+N) {if((ll)*(AA+i)==1) {A[i]=true;}}
	vector<ll> trash; set<ll> good; REP(i,0,K) {if(A[i]) {good.insert(i);} else {trash.pb(i);}}
	ll needed;
	REP(i,0,N)
	{
		needed=GetRequest();
		if(good.find(needed)!=good.end())
		{
			if(!A[K+i]) {good.erase(good.find(needed)); trash.pb(needed);}
		}
		else
		{
			PutBack(trash.back()); trash.pop_back();
			if(A[K+i]) {good.insert(needed);} else {trash.pb(needed);}
		}
	}
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 508 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 2 ms 772 KB Output is correct
4 Correct 3 ms 932 KB Output is correct
5 Correct 4 ms 1088 KB Output is correct
6 Correct 4 ms 1084 KB Output is correct
7 Correct 7 ms 1204 KB Output is correct
8 Correct 5 ms 1176 KB Output is correct
9 Correct 4 ms 1216 KB Output is correct
10 Correct 6 ms 1340 KB Output is correct
11 Correct 6 ms 1216 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1872 KB Output is correct
2 Correct 50 ms 6508 KB Output is correct
3 Correct 147 ms 15352 KB Output is correct
4 Correct 77 ms 11108 KB Output is correct
5 Correct 93 ms 11068 KB Output is correct
6 Correct 116 ms 11884 KB Output is correct
7 Correct 122 ms 13492 KB Output is correct
8 Correct 96 ms 12092 KB Output is correct
9 Correct 76 ms 11552 KB Output is correct
10 Correct 138 ms 14376 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 10436 KB Output is correct
2 Correct 150 ms 13880 KB Output is correct
3 Correct 140 ms 14128 KB Output is correct
4 Correct 135 ms 14156 KB Output is correct
5 Correct 152 ms 13660 KB Output is correct
6 Correct 133 ms 13956 KB Output is correct
7 Correct 133 ms 14272 KB Output is correct
8 Correct 103 ms 13736 KB Output is correct
9 Correct 137 ms 14924 KB Output is correct
10 Correct 153 ms 14136 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1180 KB Output is correct
2 Correct 4 ms 1212 KB Output is correct
3 Correct 4 ms 1080 KB Output is correct
4 Correct 4 ms 1076 KB Output is correct
5 Correct 4 ms 1084 KB Output is correct
6 Correct 5 ms 1080 KB Output is correct
7 Correct 5 ms 1204 KB Output is correct
8 Correct 7 ms 1204 KB Output is correct
9 Correct 6 ms 1212 KB Output is correct
10 Correct 7 ms 1568 KB Output is correct

Subtask #5
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 12488 KB Output is correct - 120000 bits used
2 Correct 130 ms 12740 KB Output is correct - 122000 bits used
3 Correct 138 ms 12784 KB Output is correct - 125000 bits used
4 Correct 143 ms 12864 KB Output is correct - 125000 bits used
5 Correct 140 ms 12888 KB Output is correct - 125000 bits used
6 Correct 135 ms 12764 KB Output is correct - 125000 bits used
7 Correct 131 ms 12816 KB Output is correct - 124828 bits used
8 Correct 130 ms 12836 KB Output is correct - 124910 bits used
9 Correct 143 ms 12932 KB Output is correct - 125000 bits used
10 Correct 114 ms 12676 KB Output is correct - 125000 bits used