Submission #641064

#	Time	Username	Problem	Language	Result	Execution time	Memory
641064		ymm	Unscrambling a Messy Bug (IOI16_messy)	C++17	100 / 100	2 ms	468 KiB

messy

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;
#include "messy.h"

int ans[1024];

bool ask(int n, vector<int> v, int i)
{
	string s(n, '1');
	Loop (j,0,v.size())
		if (j != i)
			s[v[j]] = '0';
	return check_element(s);
}
	

void solve(int n, vector<int> vec, int bit)
{
	assert((vec.size()<<bit) == n);
	if (vec.size() == 1)
		return;
	vector<int> v[2];
	Loop (i,0,vec.size()) {
		int tmp = ask(n, vec, i);
		v[tmp].push_back(vec[i]);
		ans[vec[i]] ^= tmp << bit;
	}
	solve(n, v[0], bit+1);
	solve(n, v[1], bit+1);
}

void make(int n, int msk, int p2bit)
{
	string s;
	Loop (i,0,n) {
		if (i%p2bit != msk)
			s.push_back('1');
		else
			s.push_back('0');
	}
	Loop (i,0,n) {
		if (i%p2bit == msk && (i&p2bit)) {
			s[i] = '1';
			add_element(s);
			s[i] = '0';
		}
	}
}

std::vector<int> restore_permutation(int n, int w, int r)
{
	for (int p2bit = 1; p2bit < n; p2bit *= 2) {
		Loop (msk,0,p2bit)
			make(n, msk, p2bit);
	}
	compile_set();
	vector<int> kooft(n);
	iota(kooft.begin(), kooft.end(), 0);
	solve(n, kooft, 0);
	return vector<int>(ans, ans+n);
}

Compilation message (stderr)

messy.cpp: In function 'bool ask(int, std::vector<int>, int)':
messy.cpp:2:40: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    2 | #define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
      |                                        ^
messy.cpp:15:2: note: in expansion of macro 'Loop'
   15 |  Loop (j,0,v.size())
      |  ^~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from messy.cpp:1:
messy.cpp: In function 'void solve(int, std::vector<int>, int)':
messy.cpp:24:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   24 |  assert((vec.size()<<bit) == n);
      |         ~~~~~~~~~~~~~~~~~~^~~~
messy.cpp:2:40: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    2 | #define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
      |                                        ^
messy.cpp:28:2: note: in expansion of macro 'Loop'
   28 |  Loop (i,0,vec.size()) {
      |  ^~~~

• Subtask 1: 20 / 20
• Subtask 2: 18 / 18
• Subtask 3: 11 / 11
• Subtask 4: 21 / 21
• Subtask 5: 30 / 30