#include<bits/stdc++.h>
#include "grader.h"
#define st first
#define nd second
#define pb push_back
#define ppb pop_back
#define umax(x,y) x=max(x,y)
#define umin(x,y) x=min(x,y)
#define ll long long
#define ii pair<int,int>
#define iii pair<int,ii>
#define sz(x) ((int) x.size())
#define orta ((bas+son)>>1)
#define all(x) x.begin(),x.end()
#define dbgs(x) cerr<<(#x)<<" --> "<<(x)<<" "
#define dbg(x) cerr<<(#x)<<" --> "<<(x)<<endl;getchar()
#define pw(x) (1<<(x))
#define inf 2000000000
#define MOD 1000000007
#define MAX 10000006
#define LOG 22
using namespace std;
int MX,placed,wbplaced;
bool okey[505];
int puton[505];
vector<int> q[2];
void find_nos() {
bool flag0=true,flag1=true;
q[0].pb(0);
q[1].pb(1);
int tot=0;
while(tot<MX) {
if(flag0) {
if(isSubsequence(q[0])){
q[0].pb(0);
tot++;
}
else flag0=false;
}
if(flag1) {
if(isSubsequence(q[1])) {
q[1].pb(1);
tot++;
}
else flag1=false;
}
}
}
void check_unique(int& put) {
int tot=0;
int plc;
for(int i=1;i<=sz(q[placed]);i++) if(okey[i]) tot++,plc=i;
if(tot==1) {
while(put<MX) {
put++;
puton[plc]++;
}
return ;
}
}
bool make_query(int pos,int turn,int putt) {
int bas=0,son=0;
int tot=0;
int top=inf;
int l,r;
int totok=0;
vector<int> qu;
for(int i=0;i<pos;i++) {
if(bas!=0) {
tot-=puton[bas];
totok-=okey[bas];
}
bas++;
son=max(son,bas-1);
while(tot+(MX-putt)*(totok>0)<turn) {
son++;
tot+=puton[son];
if(okey[son] && son!=pos) totok++;
}
if(i+sz(q[placed])-son+1<top && sz(q[placed])-son+1<=sz(q[placed])-pos) {
top=i+sz(q[placed])-son+1;
l=i;r=sz(q[placed])-son+1;
}
}
for(int i=0;i<l;i++) qu.pb(placed);
for(int i=0;i<turn;i++) qu.pb(wbplaced);
for(int i=0;i<r;i++) qu.pb(placed);
/* printf("Turn is-->%d pos is-->%d\n",turn,pos);
for(int i=0;i<sz(qu);i++) printf("%d ",qu[i]);
puts("");*/
return isSubsequence(qu);
}
vector < int > findSequence (int N) {
srand(time(NULL));
MX=N;
find_nos();
placed=1;
wbplaced=0;
if(sz(q[0])<sz(q[1])) swap(placed,wbplaced);
// printf("%d %d\n",placed,wbplaced);
// printf("%d\n",sz(q[placed])-1);
//getchar();getchar();getchar();
//exit(0);
int putt=sz(q[placed])-1;
for(int i=1;i<=sz(q[placed]);i++) okey[i]=true;
int turn=1;
vector<int> gez;
for(int i=1;i<=sz(q[placed]);i++) gez.pb(i);
while(putt<N) {
// printf("--Turn %d--\n",turn);
random_shuffle(all(gez));
for(int ind=sz(q[placed])-1;ind>=0;ind--) {
int i=gez[ind];
if(!okey[i]) continue ;
bool res=make_query(i,turn,putt);
if(!res) okey[i]=false;
else {
// printf("OK -- >%d\n",i);
putt++;
puton[i]++;
}
check_unique(putt);
if(putt==N) break ;
}
/*for(int i=1;i<=sz(q[placed]);i++) {
printf("%d ",puton[i]);
}*/
// printf("--------------\n");
turn++;
}
vector<int> ans;
for(int i=1;i<=sz(q[placed]);i++) {
for(int j=0;j<puton[i];j++) ans.pb(wbplaced);
if(i==sz(q[placed])) return ans;
ans.pb(placed);
}
}
Compilation message
hidden.cpp: In function 'std::vector<int> findSequence(int)':
hidden.cpp:233:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
hidden.cpp: In function 'bool make_query(int, int, int)':
hidden.cpp:137:15: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
for(int i=0;i<r;i++) qu.pb(placed);
~^~
hidden.cpp:133:15: warning: 'l' may be used uninitialized in this function [-Wmaybe-uninitialized]
for(int i=0;i<l;i++) qu.pb(placed);
~^~
grader.cpp: In function 'int main()':
grader.cpp:28:43: warning: format '%d' expects argument of type 'int', but argument 3 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
fprintf (fifo_out, "%d\n", ans.size ());
~~~~~~~~~~~^
grader.cpp:29:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0; i<ans.size () && i < N; i++)
~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
248 KB |
Output is correct: Maximum length of a query = 5 |
| 2 |
Correct |
2 ms |
436 KB |
Output is correct: Maximum length of a query = 6 |
| 3 |
Correct |
3 ms |
436 KB |
Output is correct: Maximum length of a query = 5 |
| 4 |
Correct |
2 ms |
436 KB |
Output is correct: Maximum length of a query = 5 |
| 5 |
Correct |
3 ms |
436 KB |
Output is correct: Maximum length of a query = 4 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
11 ms |
436 KB |
Output is partially correct: Maximum length of a query = 86 |
| 2 |
Partially correct |
10 ms |
520 KB |
Output is partially correct: Maximum length of a query = 95 |
| 3 |
Partially correct |
11 ms |
524 KB |
Output is partially correct: Maximum length of a query = 100 |
| 4 |
Partially correct |
9 ms |
524 KB |
Output is partially correct: Maximum length of a query = 80 |
| 5 |
Partially correct |
16 ms |
524 KB |
Output is partially correct: Maximum length of a query = 101 |
| 6 |
Correct |
13 ms |
524 KB |
Output is correct: Maximum length of a query = 87 |
| 7 |
Correct |
10 ms |
524 KB |
Output is correct: Maximum length of a query = 97 |
| 8 |
Partially correct |
10 ms |
524 KB |
Output is partially correct: Maximum length of a query = 90 |
| 9 |
Partially correct |
13 ms |
540 KB |
Output is partially correct: Maximum length of a query = 108 |
| 10 |
Partially correct |
8 ms |
564 KB |
Output is partially correct: Maximum length of a query = 120 |
| 11 |
Correct |
7 ms |
564 KB |
Output is correct: Maximum length of a query = 96 |
| 12 |
Correct |
9 ms |
564 KB |
Output is correct: Maximum length of a query = 100 |
| 13 |
Partially correct |
10 ms |
564 KB |
Output is partially correct: Maximum length of a query = 105 |
