oj.uz

Submission #974197

# Submission time Handle Problem Language Result Execution time Memory
974197 2024-05-03T05:50:13 Z emptypringlescan Hidden Sequence (info1cup18_hidden) C++17
87 / 100
 304 ms 668 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+2;
	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;/*
			for(; num>=0; num--){
				tst.clear();
				for(int x=0; x<j; x++) tst.push_back(use);
				for(int x=0; x<num; x++) tst.push_back(!use);
				for(int x=j; x<i; x++) tst.push_back(use);
				if(isSubsequence(tst)) break;
			}*/
			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 rep=(n-sm-len)/2;
		for(int i=0; i<=len; i++) if(oth[i]==-1) oth[i]=rep;
	}
	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
15.0 / 20.0

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

Subtask #2
72.0 / 80.0

# Verdict Execution time Memory Grader output
1 Partially correct 159 ms 436 KB Output is partially correct: Maximum length of a query = 84
2 Partially correct 187 ms 432 KB Output is partially correct: Maximum length of a query = 91
3 Partially correct 231 ms 420 KB Output is partially correct: Maximum length of a query = 97
4 Partially correct 135 ms 428 KB Output is partially correct: Maximum length of a query = 78
5 Partially correct 219 ms 432 KB Output is partially correct: Maximum length of a query = 96
6 Partially correct 163 ms 668 KB Output is partially correct: Maximum length of a query = 88
7 Partially correct 211 ms 420 KB Output is partially correct: Maximum length of a query = 98
8 Partially correct 146 ms 416 KB Output is partially correct: Maximum length of a query = 84
9 Partially correct 242 ms 424 KB Output is partially correct: Maximum length of a query = 102
10 Partially correct 261 ms 428 KB Output is partially correct: Maximum length of a query = 101
11 Partially correct 274 ms 412 KB Output is partially correct: Maximum length of a query = 97
12 Partially correct 243 ms 432 KB Output is partially correct: Maximum length of a query = 101
13 Partially correct 304 ms 420 KB Output is partially correct: Maximum length of a query = 102