oj.uz

Submission #653295

# Submission time Handle Problem Language Result Execution time Memory
653295 2022-10-26T12:12:55 Z ymm Last supper (IOI12_supper) C++17
100 / 100
 114 ms 13004 KB 
#include "advisor.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 100000;
int ans[N], ans_pos[N], ans_ptr;
int cnt[N];
vector<int> pos[N];

void ComputeAdvice(int *c, int n, int k, int m)
{
	LoopR (i,0,n)
		pos[c[i]].push_back(i);
	set<pii,greater<pii>> pq;
	Loop (i,0,k) {
		pq.insert({pos[i].size()? pos[i].back(): n, i});
		cnt[i] = 1;
		ans_pos[i] = ans_ptr++;
	}
	Loop (i,0,n) {
		if (cnt[c[i]]) {
			pq.erase({pos[c[i]].size()? pos[c[i]].back(): n, c[i]});
			cnt[c[i]]++;
			pos[c[i]].pop_back();
			pq.insert({pos[c[i]].size()? pos[c[i]].back(): n, c[i]});
			continue;
		}
		auto [_, x] = *pq.begin();
		//cerr << "c[" << i << "] = " << c[i] << " removes " << x << '\n';
		ans[ans_pos[x]] = cnt[x];
		//cerr << "ans[" << ans_pos[x] << "] = " << cnt[x] << '\n';
		cnt[x] = 0;
		pq.erase(pq.begin());
		pos[c[i]].pop_back();
		pq.insert({pos[c[i]].size()? pos[c[i]].back(): n, c[i]});
		cnt[c[i]] = 1;
		ans_pos[c[i]] = ans_ptr++;
	}
	Loop (i,0,n) {
		if (cnt[i]) {
			ans[ans_pos[i]] = cnt[i];
			//cerr << "ans[" << ans_pos[i] << "] = " << cnt[i] << '\n';
			cnt[i] = 0;
		}
	}
	Loop (i,0,ans_ptr)
		Loop (j,0,ans[i])
			WriteAdvice(i&1);
}

#include "assistant.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 100000;
int lck[N];
vector<int> zero_lck;
int n, k, r;

unsigned char *a;
int ap;
int get_bs()
{
	int x = a[ap];
	int tmp = ap;
	while (ap < r && a[ap] == x)
		++ap;
	return ap - tmp;
}

void Assist(unsigned char *_a, int _n, int _k, int _r)
{
	a = _a;
	n = _n; k = _k; r = _r;
	assert(n+k == r);
	Loop (i,0,k) {
		if (!(lck[i] = get_bs() - 1))
			zero_lck.push_back(i);
		//cerr << "lck[" << i << "] = " << lck[i] << '\n';
	}
	Loop (i,0,n) {
		int x = GetRequest();
		if (lck[x]) {
			if (!--lck[x])
				zero_lck.push_back(x);
			//cerr << "lck[" << x << "] = " << lck[x] << '\n';
		} else {
			int y = zero_lck.back();
			zero_lck.pop_back();
			//cerr << "PutBack(" << y << ")\n";
			PutBack(y);
			if (!(lck[x] = get_bs() - 1))
				zero_lck.push_back(x);
			//cerr << "lck[" << x << "] = " << lck[x] << '\n';
		}
	}
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2948 KB Output is correct
2 Correct 1 ms 2956 KB Output is correct
3 Correct 4 ms 2964 KB Output is correct
4 Correct 4 ms 3108 KB Output is correct
5 Correct 4 ms 3388 KB Output is correct
6 Correct 5 ms 3408 KB Output is correct
7 Correct 5 ms 3288 KB Output is correct
8 Correct 5 ms 3400 KB Output is correct
9 Correct 5 ms 3312 KB Output is correct
10 Correct 9 ms 3484 KB Output is correct
11 Correct 5 ms 3424 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 3660 KB Output is correct
2 Correct 41 ms 6324 KB Output is correct
3 Correct 94 ms 13004 KB Output is correct
4 Correct 67 ms 10232 KB Output is correct
5 Correct 63 ms 10280 KB Output is correct
6 Correct 81 ms 10420 KB Output is correct
7 Correct 109 ms 11576 KB Output is correct
8 Correct 73 ms 11760 KB Output is correct
9 Correct 55 ms 8976 KB Output is correct
10 Correct 112 ms 11932 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 8980 KB Output is correct
2 Correct 99 ms 11552 KB Output is correct
3 Correct 105 ms 11688 KB Output is correct
4 Correct 110 ms 11344 KB Output is correct
5 Correct 99 ms 10484 KB Output is correct
6 Correct 108 ms 11960 KB Output is correct
7 Correct 97 ms 11560 KB Output is correct
8 Correct 100 ms 12884 KB Output is correct
9 Correct 81 ms 10516 KB Output is correct
10 Correct 114 ms 11724 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3352 KB Output is correct
2 Correct 7 ms 3388 KB Output is correct
3 Correct 4 ms 3260 KB Output is correct
4 Correct 5 ms 3384 KB Output is correct
5 Correct 5 ms 3396 KB Output is correct
6 Correct 5 ms 3396 KB Output is correct
7 Correct 5 ms 3416 KB Output is correct
8 Correct 5 ms 3416 KB Output is correct
9 Correct 6 ms 3388 KB Output is correct
10 Correct 8 ms 3552 KB Output is correct

Subtask #5
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 10308 KB Output is correct - 120000 bits used
2 Correct 97 ms 10364 KB Output is correct - 122000 bits used
3 Correct 110 ms 10488 KB Output is correct - 125000 bits used
4 Correct 108 ms 10476 KB Output is correct - 125000 bits used
5 Correct 103 ms 10516 KB Output is correct - 125000 bits used
6 Correct 113 ms 10568 KB Output is correct - 125000 bits used
7 Correct 105 ms 10408 KB Output is correct - 124828 bits used
8 Correct 101 ms 10460 KB Output is correct - 124910 bits used
9 Correct 94 ms 10564 KB Output is correct - 125000 bits used
10 Correct 96 ms 11664 KB Output is correct - 125000 bits used