oj.uz

Submission #974193

# Submission time Handle Problem Language Result Execution time Memory
974193 2024-05-03T05:41:18 Z emptypringlescan Hidden Sequence (info1cup18_hidden) C++17
0 / 100
 400 ms 440 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;
	for(int j=0; j<=len; j++){
		int num=n/2+1-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<n/2+1-len){
			can=true;
			oth[j]=num;
		}
	}
	for(int i=len-1; i>=0; i--){
		for(int j=0; j<=i; j++){
			int num=n/2+1-i;
			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<n/2+1-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];
	}
	assert(ok);
	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
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct: Maximum length of a query = 5
2 Correct 0 ms 344 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 Runtime error 1 ms 432 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 440 KB Output is correct: Maximum length of a query = 83
2 Correct 190 ms 428 KB Output is correct: Maximum length of a query = 90
3 Correct 164 ms 408 KB Output is correct: Maximum length of a query = 96
4 Correct 72 ms 416 KB Output is correct: Maximum length of a query = 77
5 Correct 121 ms 436 KB Output is correct: Maximum length of a query = 95
6 Execution timed out 517 ms 416 KB Time limit exceeded
7 Halted 0 ms 0 KB -