Submission #169220

#	Time	Username	Problem	Language	Result	Execution time	Memory
169220		davitmarg	Cave (IOI13_cave)	C++17	0 / 100	1004 ms	640 KiB

cave

/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <queue>
#include <iomanip>
#include <bitset>
#include <stack>
#include <cassert>
#include <iterator>
#include <fstream>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(), v.end()
using namespace std;

const int N = 5005;

#ifndef death
#include "cave.h"
#endif


int n, used[N];

#ifdef death

int tryCombination(int a[])
{
	cout << "? ";
	for (int i = 0; i < n; i++)
		cout << a[i];
	cout << endl;
	int ans;
	cin >> ans;
	return ans;
}

void answer(int a[], int d[])
{
	cout << "! ";
	for (int i = 0; i < n; i++)
		cout << a[i];
	cout << endl;
	cout << "! ";
	for (int i = 0; i < n; i++)
		cout << d[i] << " ";
	cout << endl;
}


#endif // death

int q[N];
int query(vector<int> x)
{
	for (int i = 0; i < x.size(); i++)
		q[i] = x[i];
	return tryCombination(q);
}

int a[N], p[N];

vector<int> norm(vector<int> x)
{
	while (x.size() < n)
		x.PB(0);
	for (int i = 0; i < x.size(); i++)
		if (used[i])
			x[i] = a[i];
	return x;
}

void exploreCave(int L)
{
	n = L;
	for (int I = 0; I < n; I++)
	{
		int l=0, r=n-1, m,pos=-1;
		vector<int> x(n,0);

		int val = query(norm(x));

		if (val == -1)
		{
			for (int i = 0; i < n; i++)
				x[i] ^= 1;
			val = query(norm(x));
		}

		while (l <= r)
		{
			int m = (l + r) / 2;
			for (int i = m + 1; i < n; i++)
				x[i] ^= 1;

			int newval = query(norm(x));
			/*cout << l << " : " << r << " = "<< newval << endl;*/
			
			if (l == r)
			{
				pos = l;
				if (-1 == newval)
				{
					x[l] ^= 1;
					newval = query(norm(x));
				}
				val = newval;
				break;
			}

			if (newval == val)
				r = m;
			else
			{
				l = m + 1;
				val = newval;
			}

		}
		while (used[pos])
			pos--;
		used[pos] = 1;
		a[pos] = !x[pos];
		p[pos] = val;
	}
	answer(a, p);
}

#ifdef death

int main()
{
	int L;
	cin >> L;
	exploreCave(L);
	return 0;
}

#endif

/*



*/

Compilation message (stderr)

cave.cpp: In function 'int query(std::vector<int>)':
cave.cpp:65:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < x.size(); i++)
                  ~~^~~~~~~~~~
cave.cpp: In function 'std::vector<int> norm(std::vector<int>)':
cave.cpp:74:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (x.size() < n)
         ~~~~~~~~~^~~
cave.cpp:76:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < x.size(); i++)
                  ~~^~~~~~~~~~
cave.cpp: In function 'void exploreCave(int)':
cave.cpp:87:19: warning: unused variable 'm' [-Wunused-variable]
   int l=0, r=n-1, m,pos=-1;
                   ^

• Subtask 1: 0 / 12
• Subtask 2: 0 / 13
• Subtask 3: 0 / 21
• Subtask 4: 0 / 30
• Subtask 5: 0 / 24