Submission #974201

#	Time	Username	Problem	Language	Result	Execution time	Memory
974201		emptypringlescan	Hidden Sequence (info1cup18_hidden)	C++17	100 / 100	276 ms	664 KiB

hidden

#include <bits/stdc++.h>
using namespace std;
#include "grader.h"
vector<int> findSequence(int n){
	int use=0;
	vector<int> tst;
	for(int i=0; i<n/2+1; i++) tst.push_back(0);
	if(isSubsequence(tst)) use=1;
	int len=n/2;
	for(; len>=0; len--){
		tst.clear();
		for(int j=0; j<len; j++) tst.push_back(use);
		if(isSubsequence(tst)) break;
	} //len of use
	//cout << len << ' ' << use << '\n';
	int oth[len+1];
	memset(oth,-1,sizeof(oth));
	bool can=false;
	int yay=n/2+1;
	for(int j=0; j<=len; j++){
		int num=yay-len;
		for(; num>=0; num--){
			tst.clear();
			for(int i=0; i<j; i++) tst.push_back(use);
			for(int i=0; i<num; i++) tst.push_back(!use);
			for(int i=j; i<len; i++) tst.push_back(use);
			if(isSubsequence(tst)) break;
		}
		if(num<yay-len){
			can=true;
			oth[j]=num;
		}
	}
	for(int i=len-1; i>=0; i--){
		for(int j=0; j<=i; j++){
			int num=yay-i;
			int lo=0,hi=num,mid;
			while(lo<hi){
				mid=(lo+hi+1)/2;
				tst.clear();
				for(int x=0; x<j; x++) tst.push_back(use);
				for(int x=0; x<mid; x++) tst.push_back(!use);
				for(int x=j; x<i; x++) tst.push_back(use);
				if(isSubsequence(tst)) lo=mid;
				else hi=mid-1;
			}
			num=lo;
			if(num<yay-i){
				bool ok=true;
				int unk=-1,sm=0;
				for(int k=j; k<=j+len-i; k++){
					if(oth[k]==-1){
						if(unk!=-1) ok=false;
						else unk=k;
					}
					else sm+=oth[k];
				}
				if(ok&&unk!=-1){
					oth[unk]=num-sm;
				}
			}
		}
	}
	bool ok=true;
	int unk=-1,sm=0;
	for(int i=0; i<=len; i++){
		if(oth[i]==-1){
			if(unk!=-1) ok=false;
			else unk=i;
		}
		else sm+=oth[i];
	}
	if(!ok){
		int lar[len+1];
		for(int i=0; i<=len; i++) if(oth[i]==-1) lar[i]=yay-len;
		for(int i=len-1; i>=0; i--){
			for(int j=0; j<=i; j++){
				int num=yay-i;
				ok=true;
				unk=-1,sm=0;
				for(int k=j; k<=j+len-i; k++){
					if(oth[k]==-1){
						if(unk!=-1) ok=false;
						else unk=k;
					}
					else sm+=oth[k];
				}
				if(ok&&unk!=-1){
					lar[unk]=max(lar[unk],num-sm);
				}
			}
		}
		for(int i=0; i<=len; i++) if(oth[i]==-1) oth[i]=lar[i];
	}
	else if(unk!=-1) oth[unk]=n-sm-len;
	vector<int> ret;
	for(int i=0; i<=len; i++){
		for(int j=0; j<oth[i]; j++) ret.push_back(!use);
		ret.push_back(use);
	}
	ret.pop_back();
	return ret;
}

Compilation message (stderr)

hidden.cpp: In function 'std::vector<int> findSequence(int)':
hidden.cpp:18:7: warning: variable 'can' set but not used [-Wunused-but-set-variable]
   18 |  bool can=false;
      |       ^~~
grader.cpp: In function 'int main()':
grader.cpp:28:26: warning: format '%d' expects argument of type 'int', but argument 3 has type 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wformat=]
   28 |     fprintf (fifo_out, "%d\n", ans.size ());
      |                         ~^     ~~~~~~~~~~~
      |                          |              |
      |                          int            std::vector<int>::size_type {aka long unsigned int}
      |                         %ld
grader.cpp:29:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for (int i=0; i<ans.size () && i < N; i++)
      |                   ~^~~~~~~~~~~~

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