oj.uz

답안 #50129

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
50129 2018-06-07T16:46:02 Z Benq 최후의 만찬 (IOI12_supper) C++14
40 / 100
 786 ms 184296 KB 
#include "advisor.h"

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001;

queue<int> use[100000];
Tree<int> cur;
int nex[100000], res;
set<pi> nexUse;

/*unsigned char* A = new unsigned char[100];
int z = 0;

void WriteAdvice(int x) {
    A[z++] = x;
    cout << x << "\n";
}*/

void send(int x) {
	F0Rd(i,res) {
		if (x&(1<<i)) WriteAdvice(1);
		else WriteAdvice(0);
	}
}

int getBits(int x) {
	if (x == 1) return 0;
	return 32-__builtin_clz(x-1);
}

void ComputeAdvice(int *C, int N, int K, int M) {
	res = getBits(N);
	F0R(i,N) use[C[i]].push(i);
	F0R(i,N) {
	    nex[i] = MOD;
	    if (sz(use[i])) nex[i] = use[i].front();
	}
	F0R(i,K) {
		cur.insert(i);
		nexUse.insert({nex[i],i});
	}
	F0R(i,N) {
		if (cur.find(C[i]) == cur.end()) {
			auto a = *nexUse.rbegin();
			send(cur.order_of_key(a.s));
			cur.erase(a.s); nexUse.erase(a); 
			cur.insert(C[i]); nexUse.insert({nex[C[i]],C[i]});
		}
		nexUse.erase({nex[C[i]],C[i]});
		use[C[i]].pop();
		if (sz(use[C[i]])) nex[C[i]] = use[C[i]].front();
		else nex[C[i]] = MOD;
		nexUse.insert({nex[C[i]],C[i]});
	}

}
#include "assistant.h"

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001;

Tree<int> S;
int ind = 0;
int res;

int getBits(int x) {
	if (x == 1) return 0;
	return 32-__builtin_clz(x-1);
}

int getNex(unsigned char *A) {
	int t = 0;
	F0Rd(i,res) {
		int x = A[ind++];
		if (x) t ^= 1<<i;
	}
	return t;
}

/*int RES[4] = {2,0,3,0};
int Z = 0;

int GetRequest() { return RES[Z++]; }
void PutBack(int x) { cout << "HI " << x << "\n"; }*/

void Assist(unsigned char *A, int N, int K, int R) {
	res = getBits(N);
	F0R(i,K) S.insert(i);
	F0R(i,N) {
		int req = GetRequest();
		if (S.find(req) == S.end()) {
			int x = *S.find_by_order(getNex(A));
			S.erase(x);
			S.insert(req);
			PutBack(x);
		}
	}
}

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 71 ms 135152 KB Output is correct
2 Correct 68 ms 135888 KB Output is correct
3 Correct 71 ms 136032 KB Output is correct
4 Correct 77 ms 136032 KB Output is correct
5 Correct 86 ms 136592 KB Output is correct
6 Correct 94 ms 136592 KB Output is correct
7 Correct 74 ms 136592 KB Output is correct
8 Correct 110 ms 137256 KB Output is correct
9 Correct 97 ms 137256 KB Output is correct
10 Correct 82 ms 137256 KB Output is correct
11 Correct 87 ms 137336 KB Output is correct

Subtask #2
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 100 ms 137640 KB Output is correct
2 Correct 234 ms 141488 KB Output is correct
3 Correct 786 ms 153704 KB Output is correct
4 Correct 598 ms 153704 KB Output is correct
5 Correct 648 ms 153704 KB Output is correct
6 Correct 575 ms 153704 KB Output is correct
7 Correct 587 ms 154960 KB Output is correct
8 Correct 667 ms 156928 KB Output is correct
9 Correct 520 ms 157128 KB Output is correct
10 Correct 605 ms 159288 KB Output is correct

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 446 ms 159288 KB Output is correct
2 Correct 558 ms 160400 KB Output is correct
3 Correct 635 ms 161608 KB Output is correct
4 Correct 579 ms 162464 KB Output is correct
5 Correct 592 ms 162464 KB Output is correct
6 Correct 572 ms 165248 KB Output is correct
7 Correct 532 ms 166144 KB Output is correct
8 Correct 677 ms 170624 KB Output is correct
9 Correct 396 ms 170624 KB Output is correct
10 Correct 571 ms 170624 KB Output is correct

Subtask #4
0 / 35.0

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

Subtask #5
14.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 609 ms 170624 KB Output is partially correct - 875347 bits used
2 Partially correct 569 ms 172112 KB Output is partially correct - 841041 bits used
3 Partially correct 610 ms 173520 KB Output is partially correct - 807466 bits used
4 Partially correct 591 ms 174736 KB Output is partially correct - 806939 bits used
5 Partially correct 558 ms 175600 KB Output is partially correct - 805358 bits used
6 Partially correct 552 ms 177048 KB Output is partially correct - 807109 bits used
7 Partially correct 554 ms 178160 KB Output is partially correct - 805902 bits used
8 Partially correct 555 ms 179312 KB Output is partially correct - 808452 bits used
9 Partially correct 558 ms 180464 KB Output is partially correct - 807874 bits used
10 Partially correct 648 ms 184296 KB Output is partially correct - 1266636 bits used