Submission #169247

#	Time	Username	Problem	Language	Result	Execution time	Memory
169247		davitmarg	Cave (IOI13_cave)	C++17	100 / 100	1853 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

vector<int> ans;

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

	int mn = -1;
	for (int i = 0; i < n; i++)
		if (a[i] != ans[i])
		{
			mn = i;
			break;
		}
	cout << mn << endl;
	return mn;
}

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];
	int ret = tryCombination(q);
	if (ret == -1)
		ret = mod;
	return ret;
}

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;
}


vector<int> rev(vector<int> x)
{
	while (x.size() < n)
		x.PB(0);
	for (int i = 0; i < x.size(); i++)
		x[i] ^= 1;
	return x;
}

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

		if(last!=1)
			val = query(norm(x));
		

		if (I == n - 1)
		{
			for (int i = 0; i < n; i++)
				if (!used[i])
				{
					a[i] = (val != mod);
					p[i] = n - 1;
					break;
				}
			break;
		}

		if(last!=0)
			rval = query(norm(rev(x)));

		last = 0;
		if (val > rval)
		{
			last = 1;
			x = rev(x);
		}

		while (l <= r)
		{
			int m = (l + r) / 2;
			for (int i = m + 1; i < n; i++)
				x[i] ^= 1;
			if (query(norm(x)) != min(val,rval))
			{
				l = m+1;
			}
			else
			{
				pos = m;
				r = m - 1;
			}
			for (int i = m + 1; i < n; i++)
				x[i] ^= 1;
		}
		while (used[pos])
			pos--;
		used[pos] = 1;
		a[pos] = !x[pos];
		p[pos] = min(val,rval);
		//cout << "!!!!!!!!!!!!!!!" << pos << " : "<< a[pos] << endl;
	}
	answer(a, p);
}

#ifdef death

int main()
{
	int L;
	cin >> L;
	for (int i = 0; i < L; i++)
	{
		int x;
		cin>>x;
		ans.PB(x);
	}
	exploreCave(L);
	return 0;
}

#endif

/*



*/

Compilation message (stderr)

cave.cpp: In function 'int query(std::vector<int>)':
cave.cpp:74: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:86:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (x.size() < n)
         ~~~~~~~~~^~~
cave.cpp:88: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> rev(std::vector<int>)':
cave.cpp:97:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (x.size() < n)
         ~~~~~~~~~^~~
cave.cpp:99: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:110:19: warning: unused variable 'm' [-Wunused-variable]
   int l=0, r=n-1, m,pos=-1;
                   ^
cave.cpp:107:11: warning: 'rval' may be used uninitialized in this function [-Wmaybe-uninitialized]
  int val, rval,last=-1;
           ^~~~

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