Submission #364873

# Submission time Handle Problem Language Result Execution time Memory
364873 2021-02-10T10:31:21 Z amunduzbaev Hidden Sequence (info1cup18_hidden) C++14
100 / 100
9 ms 364 KB
#include <bits/stdc++.h>
#include "grader.h"
using namespace std;

#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define ub upper_bound
#define lb lower_bound
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(),x.rend()
#define NeedForSpeed ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//#define int long long
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii; 
typedef pair<ll, ll> pll; 
typedef vector<ll> vll;
typedef vector<int> vii;
typedef vector<pll> vpll;
typedef vector<pii> vpii;
template<class T> bool umin(T& a, const T& b) {return a > b? a = b, true:false;}
template<class T> bool umax(T& a, const T& b) {return a < b? a = b, true:false;}

#ifndef EVAL
#include "grader.cpp"
#endif

//int N;

bool ask(int a, int b, int first){
	vii tt;
	while(a--) tt.pb(first);
	while(b--) tt.pb(first ^ 1);
	//assert(sz(tt) <= N);
	//for(auto x:tt) cout<<x<<" ";
	//cout<<endl;
	return isSubsequence(tt);
}

vector<int>findSequence(int n){
	int n0 = 0, n1 = 0;
	//N = n;
	for(int i=0;i<n;i++){
		if(!ask(n0+1, 0, 0)) { n1 = n - n0; break; }
		if(!ask(n1+1, 0, 1)) { n0 = n - n1; break; }
		n1++, n0++;
	}
	
	int a0 = 0, a1 = 0;
	vii res;
	for(int i=0;i<n;i++){
		int x;
		if(a0 + n1 + 1 <= n/2+1){
			if(ask(a0+1, n1, 0)) x = 0;
			else x = 1;
		}else{
			if(ask(a1+1, n0, 1)) x = 1;
			else x = 0;
		}
		if(x) a1++, n1--;
		else a0++, n0--;
		res.pb(x);
	}
	//for(auto x:res) cout<<x<<" ";
	//cout<<"\n";
	return res;
}

/*

7
1 0 0 1 0 1 1 

*/

Compilation message

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++)
      |                   ~^~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct: Maximum length of a query = 5
2 Correct 1 ms 364 KB Output is correct: Maximum length of a query = 6
3 Correct 1 ms 364 KB Output is correct: Maximum length of a query = 5
4 Correct 1 ms 364 KB Output is correct: Maximum length of a query = 5
5 Correct 1 ms 364 KB Output is correct: Maximum length of a query = 4
# Verdict Execution time Memory Grader output
1 Correct 6 ms 364 KB Output is correct: Maximum length of a query = 83
2 Correct 8 ms 364 KB Output is correct: Maximum length of a query = 90
3 Correct 8 ms 364 KB Output is correct: Maximum length of a query = 96
4 Correct 5 ms 364 KB Output is correct: Maximum length of a query = 77
5 Correct 7 ms 364 KB Output is correct: Maximum length of a query = 95
6 Correct 6 ms 364 KB Output is correct: Maximum length of a query = 87
7 Correct 8 ms 364 KB Output is correct: Maximum length of a query = 97
8 Correct 5 ms 364 KB Output is correct: Maximum length of a query = 83
9 Correct 7 ms 364 KB Output is correct: Maximum length of a query = 101
10 Correct 9 ms 364 KB Output is correct: Maximum length of a query = 100
11 Correct 7 ms 364 KB Output is correct: Maximum length of a query = 96
12 Correct 9 ms 364 KB Output is correct: Maximum length of a query = 100
13 Correct 9 ms 364 KB Output is correct: Maximum length of a query = 101