Submission #1141764

#	Time	Username	Problem	Language	Result	Execution time	Memory
1141764		Halym2007	Hidden Sequence (info1cup18_hidden)	C++17	0 / 100	606 ms	589824 KiB

hidden

#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
#define ll long long
#define sz size()
#define ff first
#define ss second
#define pb push_back
#define pii pair <int, int>
#define dur exit(0)
#define dur1 return(0)
const int N = 2e5 + 5;

static int maxQ = 0;
static vector <int> theRealAnswer;
int a[2];
//bool isSubsequence (vector < int > v) {
//    if (v.size () > maxQ)
//        maxQ = v.size ();
//    int i = 0;
//    for (auto it : v) {
//        while (i < theRealAnswer.size () && it != theRealAnswer[i]) i++;
//        if (i == theRealAnswer.size ()) return 0;
//        i++;
//    }
//    return 1;
//}
string cyk = "bashy";
vector <int> uyt (deque <int> d) {
	vector <int> ret;
	for (int i : d) {
		ret.pb (i);
	}
	return ret;
}


bool ask (deque <int> d) {
	bool ret = isSubsequence (uyt (d));
	return ret;
}

vector <int> findSequence (int N) {
    vector <int> ans;
    deque <int> d;
    int bir = -1, nol = -1;
    while (1) {
    	d.pb (0);
    	if ((int)d.sz > N / 2 + 1) break;
    	if (!ask(d)) {
    		d.pop_back();
    		nol = (int)d.sz;
			break;
		}
	}
    if (~nol) bir = N - nol;
    else {
    	d.clear();
    	while (1) {
	    	d.pb (1);
	    	assert ((int)d.sz < N / 2 + 1);
	    	if (!ask(d)) {
	    		d.pop_back();
	    		bir = (int)d.sz;
				break;
			}
		}
		nol = N - bir;
	}
	if (bir > nol) {
		swap (bir, nol);
		a[0] = 1;
	}
	else a[1] = 1;
	assert (a[0] != a[1]);
	if (min (nol, bir) == 0) {
		for (int i = 1; i <= N; ++i) {
			ans.pb (a[0]);
		}
		return ans;
	}
	int git = 0;
	while ((int)ans.sz < N) {
		git++;
		d.clear();
		assert (git <= nol);
		for (int i = 1; i <= git; ++i) d.pb (a[0]);
		int nc = bir;
		for (int i = 1; i <= bir; ++i) {
			d.pb (a[1]);
			if (!ask (d)) {
				d.pop_back();
				nc = i - 1;
				break;
			}
		}
		for (int i = 1; i <= bir - nc; ++i) {
			ans.pb (a[1]);
		}
		bir = nc;
		ans.pb (a[0]);
		if (git == nol) {
			while ((int)d.sz < N) {
				ans.pb (a[1]);
			}
			return ans;
		}
		else if (!bir) {
			while ((int)ans.sz < N) {
				ans.pb (a[0]);
			}
			return ans;
		}
	}
    return ans;
}


//int main () {
//	freopen ("input.txt", "r", stdin);
//	int n, x;
//	scanf ("%d", &n), maxQ = 0;
//	for (int i=1; i<=n; i++)
//	    scanf ("%d", &x), theRealAnswer.push_back (x);
//	
//	vector <int> ans = findSequence (n);
//	if (ans.size () != theRealAnswer.size ()) {
//	    printf ("Different lengths\n");
//	    for (auto it : ans)
//	        printf ("%d ", it);
//	    printf ("\n");
//	    return 0;
//	}
//
//	for (int i=0; i<ans.size (); i++)
//	    if (ans[i] != theRealAnswer[i]) {
//	        printf ("WA position %d\n", i + 1);
//	        for (auto it : ans)
//	            printf ("%d ", it);
//	        printf ("\n");
//	        return 0;
//	    }
//	printf ("Ok, biggest queried length %d\n", maxQ);
//	return 0;
//}

Compilation message (stderr)

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

• Subtask 1: 0 / 20
• Subtask 2: 0 / 80