#include <bits/stdc++.h>
#include "advisor.h"
using namespace std;
//#define int long long
#define double long double
#define FOR(i, l, r, d) for(int i=(l); i<=(r); i+=(d))
#define szof(x) ((int)(x).size())
#define vi vector<int>
#define pii pair<int, int>
#define F first
#define S second
#define pb push_back
#define eb emplace_back
#define mkp make_pair
#define V st[cidx]
#define LC st[cidx*2]
#define RC st[cidx*2+1]
const int INF = 2147483647;
//const int LNF = INF*INF;
const int MOD = 1000000007;
const int mod = 998244353;
const double eps = 1e-12;
const int MAX = 100010;
vi pos[MAX]; // pos[i] = pos. of color i on scaffold
vi pos_scaff[MAX];
vi res; // the sequence A
struct Node{
int sl, sr;
int cnt, Max, Max_id;
};
Node st[4*MAX];
void build(int cidx, int cl, int cr){
V.sl = cl;
V.sr = cr;
V.cnt = 0;
V.Max = 0;
V.Max_id = 0;
if(cl < cr){
int mid = (cl + cr) / 2;
build(cidx*2, cl, mid);
build(cidx*2+1, mid+1, cr);
}
}
void modify(int cidx, int pos, int type, int val){
// type = 1: cnt
// type = 2: Max
if(pos < V.sl or V.sr < pos) return;
if(V.sl == V.sr){
if(type == 1) V.cnt += val;
if(type == 2) V.Max = val;
if(V.cnt >= 1) V.Max_id = pos;
else V.Max_id = 0;
return;
}
else{
modify(cidx*2, pos, type, val);
modify(cidx*2+1, pos, type, val);
if(LC.cnt >= 1 and RC.cnt >= 1){
if(LC.Max > RC.Max){
V.cnt = LC.cnt;
V.Max = LC.Max;
V.Max_id = LC.Max_id;
}
else{
V.cnt = RC.cnt;
V.Max = RC.Max;
V.Max_id = RC.Max_id;
}
}
else if(LC.cnt >= 1){
V.cnt = LC.cnt;
V.Max = LC.Max;
V.Max_id = LC.Max_id;
}
else if(RC.cnt >= 1){
V.cnt = RC.cnt;
V.Max = RC.Max;
V.Max_id = RC.Max_id;
}
else{
V.cnt = 0;
V.Max = 0;
V.Max_id = 0;
}
}
}
vi query(){
return {st[1].cnt, st[1].Max, st[1].Max_id};
}
int query2(int cidx, int pos){
//cerr<<"query2 "<<cidx<<", "<<pos<<endl;
if(pos < V.sl or V.sr < pos){
return 0;
}
else if(V.sl == V.sr){
return V.cnt;
}
else{
return query2(cidx*2, pos) + query2(cidx*2+1, pos);
}
}
void ComputeAdvice(int *C, int N, int K, int M){
FOR(i, 0, K-1, 1){
pos_scaff[i].pb(i);
}
FOR(i, 0, N-1, 1){
pos[C[i]].pb(i);
}
FOR(i, 0, N-1, 1){
pos[i].pb(INF);
reverse(pos[i].begin(), pos[i].end());
}
build(1, 0, N-1);
FOR(i, 0, K-1, 1){
modify(1, i, 1, 1);
}
FOR(i, 0, N-1, 1){
modify(1, i, 2, pos[i].back());
}
//cerr<<"advisor : "<<endl;
FOR(i, 0, N-1, 1){
if(query2(1, C[i]) > 0){
res.pb(K); // K -> do nothing
//cerr<<"-"<<endl;
continue;
}
vi ret = query();
assert(ret[0] > 0);
int rep = ret[2];
// add C[i], remove ret[2], upd t. of C[i]
modify(1, C[i], 1, 1);
modify(1, ret[2], 1, -1);
pos[C[i]].pop_back();
modify(1, C[i], 2, pos[C[i]].back());
// pos. on scaff
res.pb(pos_scaff[ret[2]].back());
pos_scaff[C[i]].pb(pos_scaff[ret[2]].back());
pos_scaff[ret[2]].pop_back();
//cerr<<"P "<<res.back()<<endl;
}
//cerr<<"str : ";
int sz = __lg(K + 1);
if((1<<sz) < K + 1) sz++;
for(int i : res){
FOR(j, 0, sz-1, 1){
if(i & (1<<j)) WriteAdvice(1);
else WriteAdvice(0);
//if(i & (1<<j)) cerr<<1;
//else cerr<<0;
}
}
//cerr<<endl;
}
#include <bits/stdc++.h>
#include "assistant.h"
using namespace std;
//#define int long long
#define double long double
#define FOR(i, l, r, d) for(int i=(l); i<=(r); i+=(d))
#define szof(x) ((int)(x).size())
#define vi vector<int>
#define pii pair<int, int>
#define F first
#define S second
#define pb push_back
#define eb emplace_back
#define mkp make_pair
//const int INF = 2147483647;
//const int LNF = INF*INF;
//const int MOD = 1000000007;
//const int mod = 998244353;
//const double eps = 1e-12;
//const int MAX = 100010;
int col[100010];
void Assist(unsigned char *A, int N, int K, int R){
FOR(i, 0, K-1, 1){
col[i] = i;
}
int sz = R / N;
FOR(i, 0, N-1, 1){
int newcol = GetRequest();
int val = 0;
FOR(j, 0, sz-1, 1){
if(A[i*sz + j] == 1) val += (1<<j);
}
//cerr<<"val = "<<val<<endl;
if(val < K){
PutBack(col[val]);
col[val] = newcol;
}
}
}
Compilation message
advisor.cpp: In function 'void ComputeAdvice(int*, int, int, int)':
advisor.cpp:154:13: warning: unused variable 'rep' [-Wunused-variable]
154 | int rep = ret[2];
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
5248 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
5232 KB |
Output isn't correct - not an optimal way |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
35 ms |
7460 KB |
Output isn't correct - not an optimal way |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
351 ms |
25016 KB |
Output isn't correct - not an optimal way |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
5644 KB |
Error - advice is too long |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
437 ms |
28316 KB |
Output isn't correct - not an optimal way |
| 2 |
Incorrect |
423 ms |
28372 KB |
Output isn't correct - not an optimal way |
| 3 |
Incorrect |
420 ms |
28332 KB |
Output isn't correct - not an optimal way |
| 4 |
Incorrect |
413 ms |
28500 KB |
Output isn't correct - not an optimal way |
| 5 |
Incorrect |
438 ms |
28512 KB |
Output isn't correct - not an optimal way |
| 6 |
Incorrect |
420 ms |
28528 KB |
Output isn't correct - not an optimal way |
| 7 |
Incorrect |
416 ms |
28380 KB |
Output isn't correct - not an optimal way |
| 8 |
Incorrect |
428 ms |
28420 KB |
Output isn't correct - not an optimal way |
| 9 |
Incorrect |
415 ms |
28388 KB |
Output isn't correct - not an optimal way |
| 10 |
Correct |
423 ms |
29200 KB |
Output is partially correct - 1500000 bits used |
