Submission #406340

#	Time	Username	Problem	Language	Result	Execution time	Memory
406340		Kevin_Zhang_TW	Unscrambling a Messy Bug (IOI16_messy)	C++17	100 / 100	3 ms	460 KiB

messy

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T L, T R) { while (L != R) cerr << *L << " \n"[next(L) == R], ++L; }
#else
#define DE(...) 0
#define debug(...) 0
#endif

#include "messy.h"

const int MAX_N = 128;
int n;
int pos[MAX_N];
string operator | (string a, const string &b) {
	for (int i = 0;i < a.size();++i) if (b[i] == '1')
		a[i] = '1';
	return a;
}
string to_s(vector<int> a) {
	string w(n, '0');
	for (int i : a) w[i] = '1';
	return w;
}
vector<int> operator + (vector<int> a, int b) { a.pb(b); return a; }
vector<int> operator + (vector<int> a, vector<int> b) { a.insert(end(a), AI(b)); return a; }

void gen_element(int l, int r, vector<int> all = {}) {
	if (l == r) return;
	int m = l + r >> 1;
	for (int i = l;i <= m;++i) {
		add_element(to_s(all + i));
	}
	for (int i = l;i <= m;++i)
		all.pb(i);
	gen_element(m+1, r, all);
	for (int i = l;i <= m;++i) all.pop_back();
	for (int i = m+1;i <= r;++i)
		all.pb(i);
	gen_element(l, m, all);
}
vector<int> rec_element(vector<int> item, vector<int> all = {}) {
	if (item.size() == 1) return item;
	vector<int> L, R;
	for (int i : item)
		(check_element(to_s(all + i)) ? L : R).pb(i);

	vector<int> lall = all + R, rall = all + L;

	auto A = rec_element(L, lall), B = rec_element(R, rall);

	return A + B;
}

std::vector<int> restore_permutation(int n, int w, int r) {
	static int cnt;
	assert(++cnt == 1);
	::n = n;
	gen_element(0, n-1);
    compile_set();
	vector<int> ids(n); iota(AI(ids), 0);
	vector<int> sorted = rec_element(ids);
	vector<int> per(n);
	for (int i = 0;i < n;++i)
		per[ sorted[i] ] = i;
	return per;
}

Compilation message (stderr)

messy.cpp: In function 'std::string operator|(std::string, const string&)':
messy.cpp:24:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |  for (int i = 0;i < a.size();++i) if (b[i] == '1')
      |                 ~~^~~~~~~~~~
messy.cpp: In function 'void gen_element(int, int, std::vector<int>)':
messy.cpp:38:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |  int m = l + r >> 1;
      |          ~~^~~

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