oj.uz

Submission #247559

# Submission time Handle Problem Language Result Execution time Memory
247559 2020-07-11T16:11:45 Z Pajaraja Last supper (IOI12_supper) C++17
100 / 100
 457 ms 15352 KB 
#include <bits/stdc++.h>
#define MAXN 100007
#include "advisor.h"
using namespace std;
static set<pair<pair<int,int>, int> > s;
static set<int> sk;
static int nxt[MAXN],lst[MAXN],cnt[MAXN],br=0,d[MAXN];
void ComputeAdvice(int *C, int N, int K, int M) 
{
	fill(lst,lst+N,N);
	for(int i=N-1;i>=0;i--) {nxt[i]=lst[C[i]]; lst[C[i]]=i;}
	for(int i=0;i<K;i++) {s.insert({{lst[i],i},br++}); sk.insert(i);}
	for(int i=0;i<N;i++)
	{
		int a=C[i];
		if(sk.find(a)!=sk.end()) 
		{
			cnt[a]++;
			pair<pair<int,int>,int> p=*s.lower_bound({{i,a},0});
			s.erase(p);
			p.first.first=nxt[i];
			s.insert(p);
		}
		else
		{
			set<pair<pair<int,int>,int> >::iterator it=s.end();
			it--;
			pair<pair<int,int>,int> p=*it;
			s.erase(p); sk.erase(p.first.second);
			d[p.second]=cnt[p.first.second]; cnt[p.first.second]=0;
			p={{nxt[i],a},br++};
			s.insert(p); sk.insert(a);
		}
	}
	for(set<pair<pair<int,int>,int> >::iterator it=s.begin();it!=s.end();it++)
	{
		pair<pair<int,int>,int> p=*it;
		d[p.second]=cnt[p.first.second];	
	}
	for(int i=0;i<br;i++) 
	{
		for(int j=0;j<d[i];j++) WriteAdvice(1);
		WriteAdvice(0);
	}
}
#include <bits/stdc++.h>
#define MAXN 100007
#include "assistant.h"
using namespace std;
static vector<int> d;
static queue<int> q;
static int cnt[MAXN];
void Assist(unsigned char *A, int N, int K, int R) 
{
	int t=0,p=0;
	for(int i=0;i<R;i++)
	{
		if(A[i]==1) t++;
		else {d.push_back(t); t=0;}
	}
	for(int i=0;i<K;i++) {cnt[i]=d[p++]; if(cnt[i]==0) q.push(i);}
	for(int i=0;i<N;i++)
	{
		int r=GetRequest();
		if(cnt[r]!=0) {cnt[r]--; if(cnt[r]==0) q.push(r);}
		else
		{
			cnt[r]=d[p++];
			PutBack(q.front());
			q.pop();
			if(cnt[r]==0) q.push(r);
		}
	}
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1024 KB Output is correct
2 Correct 8 ms 1024 KB Output is correct
3 Correct 11 ms 1024 KB Output is correct
4 Correct 11 ms 1192 KB Output is correct
5 Correct 13 ms 1148 KB Output is correct
6 Correct 14 ms 1284 KB Output is correct
7 Correct 14 ms 1140 KB Output is correct
8 Correct 38 ms 1292 KB Output is correct
9 Correct 16 ms 1280 KB Output is correct
10 Correct 16 ms 1536 KB Output is correct
11 Correct 15 ms 1404 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 1792 KB Output is correct
2 Correct 70 ms 4848 KB Output is correct
3 Correct 167 ms 15352 KB Output is correct
4 Correct 108 ms 7664 KB Output is correct
5 Correct 120 ms 7664 KB Output is correct
6 Correct 134 ms 8688 KB Output is correct
7 Correct 179 ms 11848 KB Output is correct
8 Correct 125 ms 12016 KB Output is correct
9 Correct 114 ms 7664 KB Output is correct
10 Correct 175 ms 14016 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 10224 KB Output is correct
2 Correct 168 ms 12840 KB Output is correct
3 Correct 190 ms 13040 KB Output is correct
4 Correct 457 ms 12784 KB Output is correct
5 Correct 161 ms 11760 KB Output is correct
6 Correct 174 ms 13040 KB Output is correct
7 Correct 175 ms 13040 KB Output is correct
8 Correct 141 ms 13040 KB Output is correct
9 Correct 175 ms 12928 KB Output is correct
10 Correct 179 ms 13040 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 1328 KB Output is correct
2 Correct 15 ms 1292 KB Output is correct
3 Correct 14 ms 1144 KB Output is correct
4 Correct 14 ms 1104 KB Output is correct
5 Correct 13 ms 1104 KB Output is correct
6 Correct 14 ms 1160 KB Output is correct
7 Correct 15 ms 1328 KB Output is correct
8 Correct 60 ms 1312 KB Output is correct
9 Correct 35 ms 1280 KB Output is correct
10 Correct 20 ms 1792 KB Output is correct

Subtask #5
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 11760 KB Output is correct - 120000 bits used
2 Correct 164 ms 12272 KB Output is correct - 122000 bits used
3 Correct 198 ms 13040 KB Output is correct - 125000 bits used
4 Correct 192 ms 12920 KB Output is correct - 125000 bits used
5 Correct 182 ms 13296 KB Output is correct - 125000 bits used
6 Correct 168 ms 13040 KB Output is correct - 125000 bits used
7 Correct 177 ms 13040 KB Output is correct - 124828 bits used
8 Correct 194 ms 13040 KB Output is correct - 124910 bits used
9 Correct 192 ms 13040 KB Output is correct - 125000 bits used
10 Correct 178 ms 13304 KB Output is correct - 125000 bits used