이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
}
}
컴파일 시 표준 에러 (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; }
~~^~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |