oj.uz

답안 #761148

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
761148 2023-06-19T09:26:15 Z NothingXD 최후의 만찬 (IOI12_supper) C++17
43 / 100
 244 ms 16856 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, lg, f[maxn];
bool mark[maxn];
vector<int> idx[maxn];
set<pii> q;
void add(int idx, int x){
	for (; idx <= n; idx += idx & -idx) f[idx] += x;
}

int get(int idx){
	int res = 0;
	for (; idx; idx -= idx & -idx) res += f[idx];
	return res;
}

void give(int x){
	for (int i = lg-1; ~i; i--){
		WriteAdvice((x >> i)&1);
	}
}

void ComputeAdvice(int *C, int N, int K, int M) {
	n = N;
	for (int i = 0; i < n; i++){
		idx[i].push_back(n);
	}
	for (int i = n-1; ~i; i--){
		idx[C[i]].push_back(i);
	}
	for (int i = 0; i < K; i++){
		q.insert({idx[i].back(), i});
		mark[i] = true;
		add(i+1, 1);
	}
	lg = 32 - __builtin_clz(K);
	for (int i = 0; i < n; i++){
		if (mark[C[i]]){
			q.erase({idx[C[i]].back(), C[i]});
			idx[C[i]].pop_back();
			q.insert({idx[C[i]].back(), C[i]});
			continue;
		}
		auto it = q.end();
		it--;
		pii tmp = *it;
		q.erase(it);
		idx[C[i]].pop_back();
		q.insert({idx[C[i]].back(), C[i]});
		give(get(tmp.S));
		add(tmp.S+1, -1);
		mark[tmp.S] = false;
		add(C[i]+1, 1);
		mark[C[i]] = true;
	}
}

#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;

int nn, F[maxn];
bool Mark[maxn];

void Add(int idx, int x){
	for (; idx <= nn; idx += idx & -idx) F[idx] += x;
}

int Find(int idx){
	int res = 0;
	for (int i = 19; ~i; i--){
		int tmp = res + (1 << i);
		if (tmp <= nn && F[tmp] < idx){
			idx -= F[tmp];
			res = tmp;
		}
	}
	return res;
}

void Assist(unsigned char *A, int N, int K, int R) {
	nn = N;
	int lg = 32 - __builtin_clz(K);
	for (int i = 0; i < K; i++){
		Mark[i] = true;
		Add(i+1, 1);
	}
	int ptr = 0;
	for (int i = 0; i < nn; i++){
		int tmp = GetRequest();
		if (Mark[tmp]) continue;
		int x = 0;
		for (int j = ptr; j < ptr + lg; j++){
			x += (A[j] << (ptr + lg - j - 1));
		}
		ptr += lg;
		int idx = Find(x+1);
		PutBack(idx);
		Add(idx+1, -1);
		Mark[idx] = false;
		Mark[tmp] = true;
		Add(tmp+1, 1);
	}
}

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2960 KB Output is correct
2 Correct 1 ms 2948 KB Output is correct
3 Correct 2 ms 2956 KB Output is correct
4 Correct 4 ms 3300 KB Output is correct
5 Correct 4 ms 3364 KB Output is correct
6 Correct 8 ms 3412 KB Output is correct
7 Correct 4 ms 3360 KB Output is correct
8 Correct 10 ms 3516 KB Output is correct
9 Correct 10 ms 3556 KB Output is correct
10 Correct 7 ms 3532 KB Output is correct
11 Correct 8 ms 3532 KB Output is correct

Subtask #2
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 3888 KB Output is correct
2 Correct 66 ms 8032 KB Output is correct
3 Correct 199 ms 16328 KB Output is correct
4 Correct 133 ms 12608 KB Output is correct
5 Correct 223 ms 14772 KB Output is correct
6 Correct 185 ms 14920 KB Output is correct
7 Correct 174 ms 14656 KB Output is correct
8 Correct 172 ms 14636 KB Output is correct
9 Correct 103 ms 12004 KB Output is correct
10 Correct 160 ms 14468 KB Output is correct

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 136 ms 12240 KB Output is correct
2 Correct 215 ms 14612 KB Output is correct
3 Correct 163 ms 14420 KB Output is correct
4 Correct 170 ms 14184 KB Output is correct
5 Correct 140 ms 13056 KB Output is correct
6 Correct 164 ms 14472 KB Output is correct
7 Correct 160 ms 14268 KB Output is correct
8 Correct 213 ms 16832 KB Output is correct
9 Correct 105 ms 13292 KB Output is correct
10 Correct 166 ms 14532 KB Output is correct

Subtask #4
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 3076 KB Error - advice is too long
2 Halted 0 ms 0 KB -

Subtask #5
17.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 182 ms 14732 KB Output is partially correct - 772365 bits used
2 Correct 166 ms 14564 KB Output is partially correct - 742095 bits used
3 Correct 164 ms 14452 KB Output is partially correct - 712470 bits used
4 Correct 181 ms 14624 KB Output is partially correct - 712005 bits used
5 Correct 166 ms 14888 KB Output is partially correct - 710610 bits used
6 Correct 195 ms 14504 KB Output is partially correct - 712155 bits used
7 Correct 193 ms 14568 KB Output is partially correct - 711090 bits used
8 Correct 169 ms 14544 KB Output is partially correct - 713340 bits used
9 Correct 173 ms 14496 KB Output is partially correct - 712830 bits used
10 Correct 244 ms 16856 KB Output is partially correct - 1117620 bits used