oj.uz

Submission #53929

# Submission time Handle Problem Language Result Execution time Memory
53929 2018-07-02T00:27:00 Z Benq Last supper (IOI12_supper) C++14
100 / 100
 633 ms 212976 KB 
#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));
}
#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 154096 KB Output is correct
2 Correct 75 ms 154576 KB Output is correct
3 Correct 97 ms 154936 KB Output is correct
4 Correct 89 ms 155456 KB Output is correct
5 Correct 83 ms 156032 KB Output is correct
6 Correct 82 ms 156032 KB Output is correct
7 Correct 83 ms 156032 KB Output is correct
8 Correct 84 ms 156408 KB Output is correct
9 Correct 94 ms 156408 KB Output is correct
10 Correct 94 ms 156624 KB Output is correct
11 Correct 96 ms 156624 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 157872 KB Output is correct
2 Correct 206 ms 165208 KB Output is correct
3 Correct 487 ms 182088 KB Output is correct
4 Correct 320 ms 182088 KB Output is correct
5 Correct 379 ms 182088 KB Output is correct
6 Correct 401 ms 182088 KB Output is correct
7 Correct 436 ms 183112 KB Output is correct
8 Correct 361 ms 183984 KB Output is correct
9 Correct 340 ms 185088 KB Output is correct
10 Correct 503 ms 187904 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 369 ms 187904 KB Output is correct
2 Correct 633 ms 188968 KB Output is correct
3 Correct 480 ms 190696 KB Output is correct
4 Correct 461 ms 190832 KB Output is correct
5 Correct 417 ms 190832 KB Output is correct
6 Correct 486 ms 193888 KB Output is correct
7 Correct 583 ms 194528 KB Output is correct
8 Correct 433 ms 198696 KB Output is correct
9 Correct 384 ms 198696 KB Output is correct
10 Correct 499 ms 198696 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 198696 KB Output is correct
2 Correct 84 ms 198696 KB Output is correct
3 Correct 87 ms 198696 KB Output is correct
4 Correct 81 ms 198696 KB Output is correct
5 Correct 93 ms 198696 KB Output is correct
6 Correct 82 ms 198696 KB Output is correct
7 Correct 83 ms 198696 KB Output is correct
8 Correct 94 ms 198696 KB Output is correct
9 Correct 86 ms 198696 KB Output is correct
10 Correct 90 ms 198696 KB Output is correct

Subtask #5
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 472 ms 199712 KB Output is correct - 120000 bits used
2 Correct 479 ms 200824 KB Output is correct - 122000 bits used
3 Correct 482 ms 202488 KB Output is correct - 125000 bits used
4 Correct 486 ms 203384 KB Output is correct - 125000 bits used
5 Correct 491 ms 204704 KB Output is correct - 125000 bits used
6 Correct 564 ms 205944 KB Output is correct - 125000 bits used
7 Correct 507 ms 207096 KB Output is correct - 124828 bits used
8 Correct 473 ms 207992 KB Output is correct - 124910 bits used
9 Correct 455 ms 209656 KB Output is correct - 125000 bits used
10 Correct 460 ms 212976 KB Output is correct - 125000 bits used