Submission #69332

#	Time	Username	Problem	Language	Result	Execution time	Memory
69332		E869120	Unscrambling a Messy Bug (IOI16_messy)	C++14	100 / 100	5 ms	512 KiB

messy

#include <vector>
#include <string>
#include <algorithm>
using namespace std;

#include "messy.h"

// ------------------------------------------ 70 点解法 -------------------------------------

int N, B;

string adds(vector<int>p) {
	string S; for (int i = 0; i < N; i++) S += "0";
	for (int i = 0; i < p.size(); i++) S[p[i]] = '1';
	return S;
}

void encode() {
	// --------------- Step 1. 0 から 6 を区別する
	for (int i = 0; i < B; i++) add_element(adds(vector<int>{i}));
	for (int i = 0; i < B - 1; i++) add_element(adds(vector<int>{i, i + 1}));
	add_element(adds(vector<int>{0, 1, 2}));
	for (int i = 0; i < B; i++) {
		for (int j = B; j < N; j++) {
			if ((j / (1 << i)) % 2 == 0) continue;
			vector<int>G; for (int k = 0; k < B; k++) { if (k != i) G.push_back(k); }
			G.push_back(j);
			add_element(adds(G));
		}
	}
}

int p[128]; vector<int>X[7], P, ZZ; bool used[7];

void brute_force(int v, int mod, vector<int>V) {
	if (V.size() == 0) return;
	if (mod == 128) { p[V[0]] = v; return; }

	vector<int>V1, V2, W; for (int i = 0; i < B; i++) { if ((1 << i) != mod) W.push_back(ZZ[P[i]]); }
	for (int i = 0; i < V.size() - 1; i++) {
		vector<int>WW = W; WW.push_back(V[i]);
		if (check_element(adds(WW)) == false) V1.push_back(V[i]);
		else V2.push_back(V[i]);
	}
	int c1 = 0;
	for (int i = B; i < N; i++) { if (i % (mod * 2) == v) c1++; }
	if (c1 != V1.size()) V1.push_back(V[V.size() - 1]);
	else V2.push_back(V[V.size() - 1]);

	brute_force(v, mod * 2, V1);
	brute_force(v + mod, mod * 2, V2);
}

void decode() {
	vector<int>Z;
	for (int i = 0; i < N; i++) { if (check_element(adds(vector<int>{i})) == true) Z.push_back(i); }
	ZZ = Z;

	// Z は 7 個ある
	for (int i = 0; i < B; i++) {
		for (int j = i + 1; j < B; j++) {
			if (check_element(adds(vector<int>{Z[i], Z[j]})) == true) { X[i].push_back(j); X[j].push_back(i); }
		}
	}
	int cx = 0;
	for (int i = 0; i < B; i++) { if (X[i].size() == 1) cx = i; }
	for (int i = 0; i < B - 1; i++) {
		used[cx] = true; P.push_back(cx);
		for (int j = 0; j < X[cx].size(); j++) { if (used[X[cx][j]] == false) { cx = X[cx][j]; break; } }
	}
	P.push_back(cx);
	if (check_element(adds(vector<int>{Z[P[0]], Z[P[1]], Z[P[2]]})) == false) reverse(P.begin(), P.end());

	for (int i = 0; i < B; i++) p[Z[P[i]]] = i;

	// ここからが本質
	vector<int>E;
	for (int i = 0; i < N; i++) {
		bool OK = false;
		for (int j = 0; j < Z.size(); j++) { if (i == Z[j]) OK = true; }
		if (OK == false) E.push_back(i);
	}

	brute_force(0, 1, E);
}

bool uses[8];

void solve_2() {
	add_element(adds(vector<int>{0}));
	for (int i = 1; i < N; i++) add_element(adds(vector<int>{i - 1, i}));

	compile_set();

	int cx = 0; p[cx] = 0;
	for (int i = 0; i < N; i++) { if (check_element(adds(vector<int>{i})) == true) cx = i; }
	
	int cnt = 0;
	while (true) {
		int px = -1; uses[cx] = true;
		for (int i = 0; i < N; i++) { if (uses[i] == false && check_element(adds(vector<int>{cx, i})) == true) px = i; }
		if (px == -1) break;
		cnt++; p[px] = cnt; cx = px;
	}
}

vector<int> restore_permutation(int n, int w, int r) {
	N = n; for (int i = 0; i <= 7; i++) { if ((1 << i) == n) B = i; }

	if (N == 4 || N == 8) {
		solve_2();
		vector<int>vec; for (int i = 0; i < N; i++) vec.push_back(p[i]);
		return vec;
	}
	else {
		encode();
		compile_set();
		decode();

		vector<int>Z; for (int i = 0; i < N; i++) Z.push_back(p[i]);
		return Z;
	}
}

Compilation message (stderr)

messy.cpp: In function 'std::__cxx11::string adds(std::vector<int>)':
messy.cpp:14:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < p.size(); i++) S[p[i]] = '1';
                  ~~^~~~~~~~~~
messy.cpp: In function 'void brute_force(int, int, std::vector<int>)':
messy.cpp:40:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < V.size() - 1; i++) {
                  ~~^~~~~~~~~~~~~~
messy.cpp:47:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (c1 != V1.size()) V1.push_back(V[V.size() - 1]);
      ~~~^~~~~~~~~~~~
messy.cpp: In function 'void decode()':
messy.cpp:69:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < X[cx].size(); j++) { if (used[X[cx][j]] == false) { cx = X[cx][j]; break; } }
                   ~~^~~~~~~~~~~~~~
messy.cpp:80:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < Z.size(); j++) { if (i == Z[j]) OK = true; }
                   ~~^~~~~~~~~~

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