oj.uz

Submission #317202

# Submission time Handle Problem Language Result Execution time Memory
317202 2020-10-29T06:05:03 Z Seanliu Hidden Sequence (info1cup18_hidden) C++14
59 / 100
 11 ms 380 KB 
#include <vector>
#include <deque>
#include <iostream>
#include "grader.h"
using namespace std;

int sma, big, cnt;

vector <int> findSequence (int N){
	int LIM = (3 * N) / 4 + 1, cnt;
   	vector<int> que;
	sma = -1;
	for(int i = 1; i <= N / 2 + 1; i++){
		que.push_back(0);
		if(!isSubsequence(que)){
			sma = 0;
			big = 1;
			cnt = i - 1;
			break;
		}
	}
	vector<int>().swap(que);
	if(sma == -1){
		for(int i = 1; i <= N / 2 + 1; i++){
			que.push_back(1);
			if(!isSubsequence(que)){
				sma = 1;
				big = 0;
				cnt = i - 1;
				break;
			}
		}
	}
	//cout << "Found smal = " << sma << ", cnt = " << cnt << endl;
	vector<int>().swap(que);
	if(!cnt){
		for(int i = 0; i < N; i++) que.push_back(big);
		return que;
	}
	for(int i = 0; i < cnt; i++) que.push_back(sma);
	vector<int> lens, bigs;
	lens.push_back(0);
	for(int i = 1; i < cnt; i++){
		que.insert(que.begin() + i, big);	
		if(isSubsequence(que)){
			lens.push_back(i);	
		}
		que.erase(que.begin() + i);
	}
	//cout << "Finished finding? " << endl;
	lens.push_back(cnt);
	bigs.resize(lens.size());
	int backInd = -1, used = 0;
	vector<int>().swap(que);
	for(int i = 0; i < cnt; i++) que.push_back(sma);
	for(int i = 0; i < lens.size(); i++){
		//cout<< "lens[" << i << "] = " << lens[i] << endl;
		int cnt = 0;
		while(que.size() < LIM && isSubsequence(que)){
			cnt++;	
			que.insert(que.begin() + lens[i], big);
		}
		if(isSubsequence(que)){
			backInd = i;
			//cout << "backind = " << backInd << endl;
		} else {
			bigs[i] = cnt - 1;
			used += bigs[i];
		}
		while(que.size() > lens[i] && que[lens[i]] == big){
			que.erase(que.begin() + lens[i]);
		}
	}
	//cout << "Finished finding big" << endl;
	if(backInd != -1){
		//cout << "bigs = " << N - cnt - used << endl;
		bigs[backInd] = N - cnt - used;
	}
	vector<int> ans;
	for(int i = 0; i < bigs.size(); i++){
		for(int j = 0; j < (!i ? lens[i] : lens[i] - lens[i - 1]); j++) ans.push_back(sma); 
		for(int j = 0; j < bigs[i]; j++) ans.push_back(big);	
	}
	return ans;
}

Compilation message

hidden.cpp: In function 'std::vector<int> findSequence(int)':
hidden.cpp:56:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |  for(int i = 0; i < lens.size(); i++){
      |                 ~~^~~~~~~~~~~~~
hidden.cpp:59:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   59 |   while(que.size() < LIM && isSubsequence(que)){
      |         ~~~~~~~~~~~^~~~~
hidden.cpp:70:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} [-Wsign-compare]
   70 |   while(que.size() > lens[i] && que[lens[i]] == big){
hidden.cpp:80:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |  for(int i = 0; i < bigs.size(); i++){
      |                 ~~^~~~~~~~~~~~~
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 1 ms 256 KB Output is partially correct: Maximum length of a query = 7
2 Partially correct 1 ms 256 KB Output is partially correct: Maximum length of a query = 8
3 Partially correct 1 ms 256 KB Output is partially correct: Maximum length of a query = 7
4 Partially correct 1 ms 256 KB Output is partially correct: Maximum length of a query = 7
5 Partially correct 1 ms 256 KB Output is partially correct: Maximum length of a query = 6

Subtask #2
44.0 / 80.0

# Verdict Execution time Memory Grader output
1 Partially correct 6 ms 380 KB Output is partially correct: Maximum length of a query = 86
2 Partially correct 8 ms 256 KB Output is partially correct: Maximum length of a query = 92
3 Partially correct 7 ms 256 KB Output is partially correct: Maximum length of a query = 102
4 Partially correct 7 ms 256 KB Output is partially correct: Maximum length of a query = 87
5 Partially correct 10 ms 256 KB Output is partially correct: Maximum length of a query = 103
6 Partially correct 7 ms 256 KB Output is partially correct: Maximum length of a query = 130
7 Partially correct 6 ms 256 KB Output is partially correct: Maximum length of a query = 145
8 Partially correct 4 ms 372 KB Output is partially correct: Maximum length of a query = 124
9 Partially correct 8 ms 256 KB Output is partially correct: Maximum length of a query = 126
10 Partially correct 8 ms 256 KB Output is partially correct: Maximum length of a query = 125
11 Partially correct 11 ms 256 KB Output is partially correct: Maximum length of a query = 97
12 Partially correct 6 ms 256 KB Output is partially correct: Maximum length of a query = 150
13 Partially correct 7 ms 376 KB Output is partially correct: Maximum length of a query = 107