oj.uz

Submission #1012105

# Submission time Handle Problem Language Result Execution time Memory
1012105 2024-07-01T16:11:03 Z AmirAli_H1 Last supper (IOI12_supper) C++17
100 / 100
 45 ms 12504 KB 
// In the name of Allah

#include <bits/stdc++.h>
using namespace std;

typedef		long long int			ll;
typedef		long double				ld;
typedef		pair<int, int>			pii;
typedef		pair<ll, ll>			pll;
typedef		complex<ld>				cld;

#define		all(x)					(x).begin(),(x).end()
#define		len(x)					((ll) (x).size())
#define		F						first
#define		S						second
#define		pb						push_back
#define		sep						' '
#define		endl					'\n'
#define		Mp						make_pair
#define		kill(x)					cout << x << '\n', exit(0)
#define		set_dec(x)				cout << fixed << setprecision(x);
#define		file_io(x,y)			freopen(x, "r", stdin); freopen(y, "w", stdout);

static int n, k, m;
const static int maxn = 2e5 + 7;
static int A[maxn], val[maxn], ind[maxn];
static int M[maxn], res[maxn];
static priority_queue<pii> qu;
static int mark[maxn];

void WriteAdvice(unsigned char a);

void ComputeAdvice(int C[], int Nx, int Kx, int Mx) {
	n = Nx; k = Kx; m = Mx;
	n += k;
	
	for (int i = 0; i < k; i++) A[i] = i;
	for (int i = k; i < n; i++) A[i] = C[i - k];
	
	fill(ind, ind + n, n);
	for (int i = n - 1; i >= 0; i--) {
		val[i] = ind[A[i]];
		ind[A[i]] = i;
	}
	
	fill(mark, mark + n, 0);
	while (!qu.empty()) qu.pop();
	fill(M, M + n, -1); fill(res, res + n, 1);
	for (int i = 0; i < k; i++) {
		qu.push(Mp(val[i], i));
		mark[i] = 1; M[A[i]] = i;
	}
	for (int i = k; i < n; i++) {
		while (!qu.empty()) {
			auto f = qu.top(); int r = f.S;
			if (mark[r]) break;
			else qu.pop();
		}
		
		int j = M[A[i]];
		if (j != -1) {
			mark[j] = 0;
		}
		else {
			auto f = qu.top(); qu.pop();
			int r = f.S; mark[r] = 0;
			res[r] = 0; M[A[r]] = -1;
		}
		qu.push(Mp(val[i], i));
		mark[i] = 1; M[A[i]] = i;
	}
	
	for (int i = 0; i < n; i++) {
		if (res[i]) WriteAdvice(1);
		else WriteAdvice(0);
	}
}
// In the name of Allah

#include <bits/stdc++.h>
using namespace std;

typedef		long long int			ll;
typedef		long double				ld;
typedef		pair<int, int>			pii;
typedef		pair<ll, ll>			pll;
typedef		complex<ld>				cld;

#define		all(x)					(x).begin(),(x).end()
#define		len(x)					((ll) (x).size())
#define		F						first
#define		S						second
#define		pb						push_back
#define		sep						' '
#define		endl					'\n'
#define		Mp						make_pair
#define		kill(x)					cout << x << '\n', exit(0)
#define		set_dec(x)				cout << fixed << setprecision(x);
#define		file_io(x,y)			freopen(x, "r", stdin); freopen(y, "w", stdout);

static int n, k, m;
const static int maxn = 2e5 + 7;
static int A[maxn], M[maxn];
static vector<int> ls;
static int mark[maxn];

void PutBack(int T);

int GetRequest();

void Assist(unsigned char res[], int Nx, int Kx, int Rx) {
	n = Nx; k = Kx; m = Rx;
	n += k;
	
	fill(mark, mark + n, 0); ls.clear();
	fill(M, M + n, -1);
	for (int i = 0; i < k; i++) {
		if (res[i] == 0) {
			ls.pb(i); mark[i] = 1;
		}
		A[i] = i; M[A[i]] = i;
	}
	
	for (int i = k; i < n; i++) {
		while (!ls.empty()) {
			int r = ls.back();
			if (mark[r]) break;
			else ls.pop_back();
		}
		
		A[i] = GetRequest();
		if (M[A[i]] != -1) {
			int j = M[A[i]]; mark[j] = 0;
			M[A[i]] = -1;
		}
		else {
			int j = ls.back();
			ls.pop_back(); mark[j] = 0;
			M[A[j]] = -1; PutBack(A[j]);
		}
		if (res[i] == 0) {
			ls.pb(i); mark[i] = 1;
		}
		M[A[i]] = i;
	}
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6932 KB Output is correct
2 Correct 1 ms 6936 KB Output is correct
3 Correct 1 ms 7040 KB Output is correct
4 Correct 2 ms 6964 KB Output is correct
5 Correct 3 ms 6988 KB Output is correct
6 Correct 3 ms 7076 KB Output is correct
7 Correct 3 ms 7252 KB Output is correct
8 Correct 3 ms 6996 KB Output is correct
9 Correct 3 ms 7084 KB Output is correct
10 Correct 3 ms 7136 KB Output is correct
11 Correct 3 ms 7252 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7316 KB Output is correct
2 Correct 20 ms 9544 KB Output is correct
3 Correct 40 ms 12016 KB Output is correct
4 Correct 33 ms 11052 KB Output is correct
5 Correct 33 ms 11276 KB Output is correct
6 Correct 38 ms 11532 KB Output is correct
7 Correct 40 ms 12140 KB Output is correct
8 Correct 37 ms 11128 KB Output is correct
9 Correct 38 ms 11092 KB Output is correct
10 Correct 42 ms 12048 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 11260 KB Output is correct
2 Correct 41 ms 12052 KB Output is correct
3 Correct 40 ms 12276 KB Output is correct
4 Correct 42 ms 12264 KB Output is correct
5 Correct 45 ms 12024 KB Output is correct
6 Correct 40 ms 11296 KB Output is correct
7 Correct 37 ms 12032 KB Output is correct
8 Correct 38 ms 11296 KB Output is correct
9 Correct 34 ms 12504 KB Output is correct
10 Correct 36 ms 12100 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7240 KB Output is correct
2 Correct 3 ms 7256 KB Output is correct
3 Correct 3 ms 6988 KB Output is correct
4 Correct 2 ms 5208 KB Output is correct
5 Correct 2 ms 5084 KB Output is correct
6 Correct 3 ms 5204 KB Output is correct
7 Correct 3 ms 5208 KB Output is correct
8 Correct 3 ms 5200 KB Output is correct
9 Correct 3 ms 5264 KB Output is correct
10 Correct 3 ms 7252 KB Output is correct

Subtask #5
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 11264 KB Output is correct - 120000 bits used
2 Correct 40 ms 11176 KB Output is correct - 122000 bits used
3 Correct 40 ms 12216 KB Output is correct - 125000 bits used
4 Correct 44 ms 12208 KB Output is correct - 125000 bits used
5 Correct 40 ms 11952 KB Output is correct - 125000 bits used
6 Correct 39 ms 11956 KB Output is correct - 125000 bits used
7 Correct 43 ms 12072 KB Output is correct - 124828 bits used
8 Correct 41 ms 11996 KB Output is correct - 124910 bits used
9 Correct 40 ms 12060 KB Output is correct - 125000 bits used
10 Correct 37 ms 11704 KB Output is correct - 125000 bits used