oj.uz

Submission #974201

# Submission time Handle Problem Language Result Execution time Memory
974201 2024-05-03T06:11:32 Z emptypringlescan Hidden Sequence (info1cup18_hidden) C++17
100 / 100
 276 ms 664 KB 
#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

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct: Maximum length of a query = 5
2 Correct 1 ms 592 KB Output is correct: Maximum length of a query = 6
3 Correct 0 ms 344 KB Output is correct: Maximum length of a query = 5
4 Correct 0 ms 344 KB Output is correct: Maximum length of a query = 5
5 Correct 0 ms 344 KB Output is correct: Maximum length of a query = 4

Subtask #2
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 440 KB Output is correct: Maximum length of a query = 83
2 Correct 198 ms 436 KB Output is correct: Maximum length of a query = 90
3 Correct 233 ms 428 KB Output is correct: Maximum length of a query = 96
4 Correct 119 ms 412 KB Output is correct: Maximum length of a query = 77
5 Correct 243 ms 664 KB Output is correct: Maximum length of a query = 95
6 Correct 183 ms 436 KB Output is correct: Maximum length of a query = 87
7 Correct 218 ms 412 KB Output is correct: Maximum length of a query = 97
8 Correct 155 ms 424 KB Output is correct: Maximum length of a query = 83
9 Correct 240 ms 432 KB Output is correct: Maximum length of a query = 101
10 Correct 262 ms 432 KB Output is correct: Maximum length of a query = 100
11 Correct 242 ms 416 KB Output is correct: Maximum length of a query = 96
12 Correct 262 ms 436 KB Output is correct: Maximum length of a query = 100
13 Correct 276 ms 428 KB Output is correct: Maximum length of a query = 101