oj.uz

Submission #358591

# Submission time Handle Problem Language Result Execution time Memory
358591 2021-01-25T23:15:46 Z super_j6 Last supper (IOI12_supper) C++14
100 / 100
 94 ms 8700 KB 
#include "advisor.h"
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string.h>
#include <vector>
#include <queue>
using namespace std;
#define endl '\n'
#define ll long long
#define pi pair<int, int>
#define f first
#define s second

const int mxn = 200000;
int b[mxn], f[mxn], p[mxn], ans[mxn];
priority_queue<pi> pq;

//void WriteAdvice(int x){ cout << x << " ";}

void ComputeAdvice(int *a, int n, int k, int m){
	memset(b, -1, sizeof(b));
	memset(p, 0x3f, sizeof(p));
	for(int i = n - 1; ~i; i--) f[i] = p[a[i]], p[a[i]] = i;
	for(int i = 0; i < k; i++) pq.push({p[i], b[i] = i});
	for(int i = 0; i < n; i++){
		if(~b[a[i]]) ans[b[a[i]]] = 1;
		else b[pq.top().s] = -1, pq.pop();
		b[a[i]] = i + k, pq.push({f[i], a[i]});
	}
	for(int i = 0; i < n + k; i++) WriteAdvice(ans[i]);
}
/*
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int n, m, k;
	cin >> n >> k >> m;
	
	int a[n];
	for(int i = 0; i < n; i++) cin >> a[i];
	
	ComputeAdvice(a, n, k, m);
	
	cout << endl;
	
	return 0;
}
*/
#include "assistant.h"
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
using namespace std;
#define endl '\n'
#define ll long long
#define pi pair<int, int>
#define f first
#define s second

const int mxn = 100000;
int f[mxn];
stack<int> v;
/*
int GetRequest(){
	int x;
	cin >> x;
	return x;
}

void PutBack(int x){ cout << x << " ";}
*/
void Assist(unsigned char *a, int n, int k, int m){
	for(int i = 0; i < k; i++){
		f[i] = 1;
		if(!a[i]) v.push(i);
	} 
	for(int i = 0; i < n; i++){
		int x = GetRequest();
		if(!f[x]) f[v.top()] = 0, PutBack(v.top()), v.pop();
		if(!a[k + i]) v.push(x);
		f[x] = 1;
	}
}
/*
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
 
	int n, m, k;
	cin >> n >> k >> m;
 
	unsigned char a[m];
	for(int i = 0, x; i < m; i++) cin >> x, a[i] = x;
 
	Assist(a, n, k, m);
	
	cout << endl;
 
	return 0;
}
*/

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2600 KB Output is correct
2 Correct 1 ms 2408 KB Output is correct
3 Correct 3 ms 2464 KB Output is correct
4 Correct 4 ms 2680 KB Output is correct
5 Correct 5 ms 2608 KB Output is correct
6 Correct 5 ms 2608 KB Output is correct
7 Correct 5 ms 2608 KB Output is correct
8 Correct 6 ms 2656 KB Output is correct
9 Correct 6 ms 2480 KB Output is correct
10 Correct 6 ms 2612 KB Output is correct
11 Correct 6 ms 2736 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 2864 KB Output is correct
2 Correct 38 ms 5424 KB Output is correct
3 Correct 80 ms 8196 KB Output is correct
4 Correct 68 ms 7524 KB Output is correct
5 Correct 69 ms 7576 KB Output is correct
6 Correct 75 ms 7936 KB Output is correct
7 Correct 78 ms 8296 KB Output is correct
8 Correct 67 ms 7112 KB Output is correct
9 Correct 66 ms 7228 KB Output is correct
10 Correct 82 ms 8700 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 6412 KB Output is correct
2 Correct 80 ms 8580 KB Output is correct
3 Correct 80 ms 8504 KB Output is correct
4 Correct 79 ms 8480 KB Output is correct
5 Correct 75 ms 8468 KB Output is correct
6 Correct 81 ms 8476 KB Output is correct
7 Correct 79 ms 8432 KB Output is correct
8 Correct 78 ms 7864 KB Output is correct
9 Correct 77 ms 8448 KB Output is correct
10 Correct 80 ms 8512 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2436 KB Output is correct
2 Correct 6 ms 2640 KB Output is correct
3 Correct 5 ms 2608 KB Output is correct
4 Correct 7 ms 2608 KB Output is correct
5 Correct 6 ms 2664 KB Output is correct
6 Correct 6 ms 2656 KB Output is correct
7 Correct 6 ms 2608 KB Output is correct
8 Correct 6 ms 2608 KB Output is correct
9 Correct 6 ms 2868 KB Output is correct
10 Correct 6 ms 2744 KB Output is correct

Subtask #5
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 7584 KB Output is correct - 120000 bits used
2 Correct 79 ms 7212 KB Output is correct - 122000 bits used
3 Correct 79 ms 7088 KB Output is correct - 125000 bits used
4 Correct 79 ms 7252 KB Output is correct - 125000 bits used
5 Correct 80 ms 7216 KB Output is correct - 125000 bits used
6 Correct 82 ms 7132 KB Output is correct - 125000 bits used
7 Correct 80 ms 7216 KB Output is correct - 124828 bits used
8 Correct 80 ms 7216 KB Output is correct - 124910 bits used
9 Correct 94 ms 7416 KB Output is correct - 125000 bits used
10 Correct 77 ms 6816 KB Output is correct - 125000 bits used