Submission #53929

#	Time	Username	Problem	Language	Result	Execution time	Memory
53929		Benq	Last supper (IOI12_supper)	C++14	100 / 100	633 ms	212976 KiB

advisor

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

#include "advisor.h"

queue<int> use[MX];
int nex[MX], res;
set<pi> nexUse;
set<int> del[MX], USE[MX], cur;
 
/*unsigned char* A = new unsigned char[100];
int z = 0;
 
void WriteAdvice(int x) {
    A[z++] = x;
    cout << x << "\n";
}*/
 
int cat(int col, int ti) {
    auto it0 = USE[col].ub(ti);
    auto it1 = del[col].ub(ti);
    if (it0 == USE[col].end()) return 0;
    if (it1 == del[col].end()) return 1;
    return *it0 < *it1;
}

void ComputeAdvice(int *C, int N, int K, int M) {
	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) {
		USE[C[i]].insert(i);
		if (cur.find(C[i]) == cur.end()) {
			auto a = *nexUse.rbegin();
			cur.erase(a.s); nexUse.erase(a); 
			del[a.s].insert(i);
			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]});
	}
	F0R(i,K) WriteAdvice(cat(i,-1));
	F0R(i,N) WriteAdvice(cat(C[i],i));
}

assistant

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

#include "assistant.h"

/*int C[4] = {2,0,3,0};
int IND = 0;

int GetRequest() {
	return C[IND++];
}

void PutBack(int x) {
	cout << "BAD " << x << "\n";
}*/

int ind = 0;
int getNex(unsigned char *A) { return A[ind++]; }

set<int> canDelete, S;

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

• Subtask 1: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 35 / 35
• Subtask 5: 39 / 39