oj.uz

Submission #578698

# Submission time Handle Problem Language Result Execution time Memory
578698 2022-06-17T16:16:40 Z WongChun1234 Last supper (IOI12_supper) C++14
100 / 100
 155 ms 74796 KB 
#include "advisor.h"
#include<bits/stdc++.h>
using namespace std;
int c[100050],curr[100050],lpos[100050],opt[200050];
deque<int> ap[100050];
priority_queue<pair<int,int>> pq;
void ComputeAdvice(int *C, int n, int k, int m) {
	for (int i=0;i<n;i++) c[i]=C[i];
	for (int i=0;i<n;i++) ap[c[i]].push_back(i);
	for (int i=0;i<n;i++) ap[i].push_back(2e9);
	for (int i=0;i<k;i++) curr[i]=lpos[i]=i,pq.push({ap[i][0],i});
	for (int i=k;i<n;i++) curr[i]=lpos[i]=-1;
	for (int i=0;i<n;i++){
		int choice;
		lpos[c[i]]=k+i;
		if (curr[c[i]]!=-1){
			choice=32767;
		}else{
			choice=curr[c[i]]=curr[pq.top().second];
			opt[lpos[pq.top().second]]=1;
			curr[pq.top().second]=-1;
			pq.pop();
		}
		while (ap[c[i]].front()<=i) ap[c[i]].pop_front();
		pq.push({ap[c[i]].front(),c[i]});
	}
	for (int i=0;i<n+k;i++) WriteAdvice(opt[i]);
}

#include "assistant.h"
#include<bits/stdc++.h>
using namespace std;
int pos[100050];
priority_queue<int> dump;
void Assist(unsigned char *A, int n, int k, int R) {
	for (int i=0;i<k;i++) pos[i]=i;
	for (int i=k;i<n;i++) pos[i]=-1;
	for (int i=0;i<k;i++) if (A[i]) dump.push(i);
	for (int i=0;i<n;i++){
		int nxt=GetRequest();
		int choice=0;
		if (pos[nxt]!=-1){
			if (A[i+k]) dump.push(nxt);
		}else{
			PutBack(dump.top());
			pos[dump.top()]=-1;
			dump.pop();
			pos[nxt]=1;
			if (A[i+k]) dump.push(nxt);
		}
	}
}

Compilation message

advisor.cpp: In function 'void ComputeAdvice(int*, int, int, int)':
advisor.cpp:15:7: warning: variable 'choice' set but not used [-Wunused-but-set-variable]
   15 |   int choice;
      |       ^~~~~~

assistant.cpp: In function 'void Assist(unsigned char*, int, int, int)':
assistant.cpp:13:7: warning: unused variable 'choice' [-Wunused-variable]
   13 |   int choice=0;
      |       ^~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 67888 KB Output is correct
2 Correct 47 ms 67932 KB Output is correct
3 Correct 45 ms 67896 KB Output is correct
4 Correct 42 ms 67944 KB Output is correct
5 Correct 46 ms 68340 KB Output is correct
6 Correct 45 ms 68164 KB Output is correct
7 Correct 55 ms 68320 KB Output is correct
8 Correct 49 ms 68544 KB Output is correct
9 Correct 45 ms 68276 KB Output is correct
10 Correct 48 ms 68336 KB Output is correct
11 Correct 48 ms 68264 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 68452 KB Output is correct
2 Correct 81 ms 71176 KB Output is correct
3 Correct 139 ms 74796 KB Output is correct
4 Correct 132 ms 73856 KB Output is correct
5 Correct 139 ms 73864 KB Output is correct
6 Correct 139 ms 74076 KB Output is correct
7 Correct 136 ms 74528 KB Output is correct
8 Correct 127 ms 73484 KB Output is correct
9 Correct 115 ms 73680 KB Output is correct
10 Correct 137 ms 74728 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 72524 KB Output is correct
2 Correct 155 ms 74752 KB Output is correct
3 Correct 136 ms 74752 KB Output is correct
4 Correct 141 ms 74728 KB Output is correct
5 Correct 122 ms 74772 KB Output is correct
6 Correct 146 ms 74672 KB Output is correct
7 Correct 144 ms 74788 KB Output is correct
8 Correct 137 ms 74244 KB Output is correct
9 Correct 143 ms 74764 KB Output is correct
10 Correct 133 ms 74692 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 68204 KB Output is correct
2 Correct 59 ms 68328 KB Output is correct
3 Correct 49 ms 68216 KB Output is correct
4 Correct 47 ms 68316 KB Output is correct
5 Correct 48 ms 68380 KB Output is correct
6 Correct 56 ms 68312 KB Output is correct
7 Correct 53 ms 68264 KB Output is correct
8 Correct 60 ms 68176 KB Output is correct
9 Correct 50 ms 68308 KB Output is correct
10 Correct 47 ms 68580 KB Output is correct

Subtask #5
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 73400 KB Output is correct - 120000 bits used
2 Correct 150 ms 73804 KB Output is correct - 122000 bits used
3 Correct 132 ms 73580 KB Output is correct - 125000 bits used
4 Correct 136 ms 73580 KB Output is correct - 125000 bits used
5 Correct 133 ms 73604 KB Output is correct - 125000 bits used
6 Correct 152 ms 73616 KB Output is correct - 125000 bits used
7 Correct 141 ms 73540 KB Output is correct - 124828 bits used
8 Correct 135 ms 73480 KB Output is correct - 124910 bits used
9 Correct 154 ms 73616 KB Output is correct - 125000 bits used
10 Correct 141 ms 73200 KB Output is correct - 125000 bits used