제출 #69323

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
69323		E869120	Unscrambling a Messy Bug (IOI16_messy)	C++14	50 / 100	5 ms	640 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; bool used[7];

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

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

	for (int i = 0; i < E.size(); i++) {
		int sum = 0;
		for (int j = 0; j < B; j++) {
			vector<int>G; for (int k = 0; k < B; k++) { if (j != k) G.push_back(Z[P[k]]); }
			G.push_back(E[i]);
			if (check_element(adds(G)) == true) sum += (1 << j);
		}
		p[E[i]] = sum;
	}
}

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

	encode();
	compile_set();
	decode();

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

컴파일 시 표준 에러 (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 decode()':
messy.cpp:49: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:60: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; }
                   ~~^~~~~~~~~~
messy.cpp:64:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < E.size(); i++) {
                  ~~^~~~~~~~~~

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