Submission #67120

#	Time	Username	Problem	Language	Result	Execution time	Memory
67120		hamzqq9	Hidden Sequence (info1cup18_hidden)	C++14	64 / 100	16 ms	680 KiB

hidden

#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]++;
			
			}

			if(putt==N) break ;

		}

		/*for(int i=1;i<=sz(q[placed]);i++) {

			printf("%d ",puton[i]);

		}*/

		check_unique(putt);

	//	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 (stderr)

hidden.cpp: In function 'std::vector<int> findSequence(int)':
hidden.cpp:232: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++)
                   ~^~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 44 / 80