oj.uz

Submission #780880

# Submission time Handle Problem Language Result Execution time Memory
780880 2023-07-12T14:13:14 Z NothingXD Last supper (IOI12_supper) C++17
100 / 100
 108 ms 12784 KB 
#include<bits/stdc++.h>
#include "advisor.h"

using namespace std;

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

void debug_out(){cerr << endl;}

template<typename H, typename... T>
void debug_out(H h, T... t){
	cerr << h << ' ';
	debug_out(t...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)

const int maxn = 1e5 + 10;

int n, k, m, res[maxn << 1], lst[maxn];
vector<int> idx[maxn];

void ComputeAdvice(int *C, int N, int K, int M) {
	n = N;
	k = K;
	m = M;
	for (int i = 0; i < n; i++){
		idx[C[i]].push_back(i);
	}
	set<pii> st;
	for (int i = 0; i < n; i++){
		idx[i].push_back(n);
		reverse(all(idx[i]));
	}
	memset(lst, -1, sizeof lst);
	for (int i = 0; i < k; i++){
		st.insert({idx[i].back(), i});
		lst[i] = i;
	}
	for (int i = 0; i < n; i++){
		if (lst[C[i]] != -1){
			st.erase({i, C[i]});
			res[lst[C[i]]] = 1;
		}
		else{
			auto it = st.end();
			it--;
			pii tmp = *it;
			st.erase(it);
			lst[tmp.S] = -1;
		}
		idx[C[i]].pop_back();
		st.insert({idx[C[i]].back(), C[i]});
		lst[C[i]] = k+i;
	}
	for (int i = 0; i < k+n; i++){
		WriteAdvice(res[i]);
	}
}

#include<bits/stdc++.h>
#include "assistant.h"

using namespace std;

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

/*void debug_out(){cerr << endl;}

template<typename H, typename... T>
void debug_out(H h, T... t){
	cerr << h << ' ';
	debug_out(t...);
}*/

#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)

const int maxn = 1e5 + 10;

bool mark[maxn];

void Assist(unsigned char *A, int N, int K, int R) {
	int n = N;
	int k = K;
	vector<int> del;
	for (int i = 0; i < k; i++){
		mark[i] = true;
		if (A[i] == 0) del.push_back(i);
	}
	for (int i = 0; i < n; i++){
		int tmp = GetRequest();
		if (!mark[tmp]){
			PutBack(del.back());
			mark[del.back()] = false;
			del.pop_back();
		}
		mark[tmp] = true;
		if (A[k+i] == 0) del.push_back(tmp);
	}
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3344 KB Output is correct
2 Correct 2 ms 3340 KB Output is correct
3 Correct 3 ms 3336 KB Output is correct
4 Correct 3 ms 3476 KB Output is correct
5 Correct 4 ms 3648 KB Output is correct
6 Correct 4 ms 3772 KB Output is correct
7 Correct 5 ms 3820 KB Output is correct
8 Correct 4 ms 3796 KB Output is correct
9 Correct 5 ms 3804 KB Output is correct
10 Correct 5 ms 3904 KB Output is correct
11 Correct 5 ms 3812 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 4148 KB Output is correct
2 Correct 36 ms 7340 KB Output is correct
3 Correct 95 ms 12784 KB Output is correct
4 Correct 56 ms 10808 KB Output is correct
5 Correct 56 ms 10764 KB Output is correct
6 Correct 65 ms 11048 KB Output is correct
7 Correct 82 ms 11940 KB Output is correct
8 Correct 56 ms 10844 KB Output is correct
9 Correct 48 ms 11200 KB Output is correct
10 Correct 89 ms 12700 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 9844 KB Output is correct
2 Correct 79 ms 11224 KB Output is correct
3 Correct 79 ms 11300 KB Output is correct
4 Correct 80 ms 11284 KB Output is correct
5 Correct 77 ms 10924 KB Output is correct
6 Correct 81 ms 12416 KB Output is correct
7 Correct 80 ms 12544 KB Output is correct
8 Correct 66 ms 11964 KB Output is correct
9 Correct 71 ms 12536 KB Output is correct
10 Correct 79 ms 12412 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3704 KB Output is correct
2 Correct 4 ms 3756 KB Output is correct
3 Correct 4 ms 3748 KB Output is correct
4 Correct 4 ms 3652 KB Output is correct
5 Correct 4 ms 3652 KB Output is correct
6 Correct 4 ms 3780 KB Output is correct
7 Correct 5 ms 3772 KB Output is correct
8 Correct 5 ms 3788 KB Output is correct
9 Correct 5 ms 3772 KB Output is correct
10 Correct 6 ms 3908 KB Output is correct

Subtask #5
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 10856 KB Output is correct - 120000 bits used
2 Correct 87 ms 11108 KB Output is correct - 122000 bits used
3 Correct 78 ms 11180 KB Output is correct - 125000 bits used
4 Correct 79 ms 11276 KB Output is correct - 125000 bits used
5 Correct 80 ms 11324 KB Output is correct - 125000 bits used
6 Correct 85 ms 11192 KB Output is correct - 125000 bits used
7 Correct 108 ms 11540 KB Output is correct - 124828 bits used
8 Correct 78 ms 11284 KB Output is correct - 124910 bits used
9 Correct 78 ms 11236 KB Output is correct - 125000 bits used
10 Correct 68 ms 10808 KB Output is correct - 125000 bits used