Submission #211327

#	Time	Username	Problem	Language	Result	Execution time	Memory
211327		ryansee	Hidden Sequence (info1cup18_hidden)	C++14	59 / 100	10 ms	384 KiB

hidden

#include "grader.h"

#include "bits/stdc++.h"
using namespace std;

#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define pb push_back
#define eb emplace_back
#define ins insert
#define ph push
#define f first
#define s second
#define cbr cerr << "hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define siz(x) ll(x.size())
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());    //can be used by calling rng() or shuffle(A, A+n, rng)
inline long long rand(long long x, long long y) { return (rng() % (y+1-x)) + x; } //inclusivesss
string inline to_string(char c) {string s(1,c);return s;} template<typename T> inline T gcd(T a,T b){ return a==0?llabs(b):gcd(b%a,a); }

typedef long long ll; 
typedef long double ld;
#define FOR(i,s,e) for(ll i=s;i<=ll(e);++i)
#define DEC(i,s,e) for(ll i=s;i>=ll(e);--i)
typedef pair<ll,ll>pi; typedef pair<ll,pi>spi; typedef pair<pi,pi>dpi;

#define LLINF ((long long)1e18)
#define INF int(1e9+1e6)
#define MAXN (300006)
ll n,zero,one;
vector<int> ans;
bool ask(vector<int> v) {
	return isSubsequence(v);
}
vector<int> findSequence(int N) {
	n=N;
    vector<int> v;
    ans.clear(), v.clear();
    FOR(i,1,n/2+1) v.pb(0);
    if(ask(v)) { // 0 is more
		one=0;
		v.clear();
		FOR(i,1,n/2){
			v.pb(1);
			if(ask(v)){
				one=i;
			}
		}
		zero=n-one;
	}else{
		zero=0;
		v.clear();
		FOR(i,1,n/2){
			v.pb(0);
			if(ask(v)) zero=i;
		}
		one=n-zero;
	}
	ll acc_z=0;
	FOR(i,1,one){
		ll z_val=-1, p=0;
		FOR(z,0,zero-acc_z){
			ll o1=i, z1=zero-acc_z-z;
			ll o2=one-i+1, z2=acc_z+z;
			assert(o1+o2+z1+z2==n+1);
			if(1){
				// assert(o1+z1<=n/2+1);
				v.clear();
				FOR(i,1,o1)v.pb(1);
				FOR(i,1,z1)v.pb(0);
				if(ask(v)){
					if(p)z_val=z-1;
					else z_val=z;
					break;
				}
			}else{
				// assert(o2+z2<=n/2+1);
				v.clear();
				FOR(i,1,z2)v.pb(0);
				FOR(i,1,o2)v.pb(1);
				if(ask(v)){
					z_val=z;
					p=1;
				}
			}
		}
		assert(~z_val);
		acc_z += z_val;
		while(z_val--) ans.pb(0);
		ans.pb(1);
	}
	while(acc_z < zero) {
		ans.pb(0), ++ acc_z;
	}
	return ans;
}
/*
10
0 0 0 1 1 1 0 0 1 0
*/

Compilation message (stderr)

grader.cpp: In function 'int main()':
grader.cpp:28:43: warning: format '%d' expects argument of type 'int', but argument 3 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
     fprintf (fifo_out, "%d\n", ans.size ());
                                ~~~~~~~~~~~^
grader.cpp:29:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0; i<ans.size () && i < N; i++)
                   ~^~~~~~~~~~~~

• Subtask 1: 15 / 20
• Subtask 2: 44 / 80