oj.uz

Submission #829958

# Submission time Handle Problem Language Result Execution time Memory
829958 2023-08-18T16:18:02 Z MODDI Last supper (IOI12_supper) C++14
100 / 100
 235 ms 79428 KB 
#include <bits/stdc++.h>
#include "advisor.h"
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;

int n;
stack<int> G[100105];
set<pii> activasion;
set<int> in_pq;
int advice[2 * 100100], out[100100];
void ComputeAdvice(int *C, int N, int K, int M) {
	n=N;
	for(int i=n-1;i>=0;i--) G[C[i]].push(i);
	for(int i=0;i<K;i++){
		int when = n+1;
	    if(!G[i].empty()) when=G[i].top();
	    activasion.insert(mp(-when, i));
	    in_pq.insert(i);
	}
	for(int i=0;i<K;i++) out[i] = i;
	for(int i=0;i<n+K;i++) advice[i] = 1;
	for(int i=0;i<n;i++){
	    G[C[i]].pop();
	    out[C[i]]=K+i;
	    if(in_pq.find(C[i])==in_pq.end()){      
	      	pii sega=*activasion.begin();
	      	activasion.erase(*activasion.begin());
	      	in_pq.erase(sega.second);
	      	advice[out[sega.second]]=0;
	    }
	    
	    int when = 0;
	    in_pq.insert(C[i]);
	    if(G[C[i]].empty()) when=n+1;
	    else when=G[C[i]].top();
	    activasion.insert(mp(-when, C[i]));
	}
	 
	for(int i=0;i<n+K;i++) WriteAdvice(advice[i]);
}
#include "assistant.h"
#include<bits/stdc++.h>
 
using namespace std;
 
void Assist(unsigned char *A, int N, int K, int R) {
	int n = N;
	set<int> odma, in;
	for(int i=0;i<K;i++){
		if(A[i] == 0)	odma.insert(i);
		
		in.insert(i);
	}
	for(int i=0;i<n;i++){
	    int adv=GetRequest();
	    if(in.find(adv)==in.end()){
	      PutBack(*odma.begin());
	      in.erase(*odma.begin());
	      odma.erase(odma.begin());
	    }
	    in.emplace(adv);
	    if(A[i+K]==0) odma.emplace(adv);
	}
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 68080 KB Output is correct
2 Correct 30 ms 68000 KB Output is correct
3 Correct 32 ms 68320 KB Output is correct
4 Correct 32 ms 68216 KB Output is correct
5 Correct 32 ms 68240 KB Output is correct
6 Correct 34 ms 68204 KB Output is correct
7 Correct 37 ms 68488 KB Output is correct
8 Correct 45 ms 68480 KB Output is correct
9 Correct 36 ms 68500 KB Output is correct
10 Correct 35 ms 68456 KB Output is correct
11 Correct 38 ms 68416 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 69088 KB Output is correct
2 Correct 89 ms 71644 KB Output is correct
3 Correct 222 ms 78884 KB Output is correct
4 Correct 117 ms 71540 KB Output is correct
5 Correct 122 ms 71892 KB Output is correct
6 Correct 142 ms 73680 KB Output is correct
7 Correct 235 ms 76864 KB Output is correct
8 Correct 142 ms 75564 KB Output is correct
9 Correct 103 ms 71628 KB Output is correct
10 Correct 207 ms 78980 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 75888 KB Output is correct
2 Correct 178 ms 77728 KB Output is correct
3 Correct 180 ms 78132 KB Output is correct
4 Correct 211 ms 78268 KB Output is correct
5 Correct 183 ms 78096 KB Output is correct
6 Correct 180 ms 78084 KB Output is correct
7 Correct 193 ms 78148 KB Output is correct
8 Correct 155 ms 76228 KB Output is correct
9 Correct 183 ms 79428 KB Output is correct
10 Correct 187 ms 78016 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 68532 KB Output is correct
2 Correct 44 ms 68552 KB Output is correct
3 Correct 35 ms 68068 KB Output is correct
4 Correct 44 ms 68240 KB Output is correct
5 Correct 35 ms 68240 KB Output is correct
6 Correct 34 ms 67992 KB Output is correct
7 Correct 44 ms 68484 KB Output is correct
8 Correct 45 ms 68400 KB Output is correct
9 Correct 42 ms 68408 KB Output is correct
10 Correct 38 ms 69028 KB Output is correct

Subtask #5
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 76968 KB Output is correct - 120000 bits used
2 Correct 183 ms 77532 KB Output is correct - 122000 bits used
3 Correct 193 ms 78128 KB Output is correct - 125000 bits used
4 Correct 190 ms 78032 KB Output is correct - 125000 bits used
5 Correct 181 ms 78196 KB Output is correct - 125000 bits used
6 Correct 176 ms 78068 KB Output is correct - 125000 bits used
7 Correct 176 ms 78028 KB Output is correct - 124828 bits used
8 Correct 194 ms 78068 KB Output is correct - 124910 bits used
9 Correct 184 ms 78064 KB Output is correct - 125000 bits used
10 Correct 164 ms 76404 KB Output is correct - 125000 bits used