| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 50129 |
2018-06-07T16:46:02 Z |
Benq |
Last supper (IOI12_supper) |
C++14 |
|
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);
}
}
}
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
77 ms |
170624 KB |
Error - advice is too long |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
