이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "messy.h"
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
//
//
//namespace helper {
//
// set<string> set_;
// bool compiled = false;
// int n;
// vector<int> p;
// int w;
// int r;
//
// int read_int() {
// int x;
// cin >> x;
// return x;
// }
//
//}
//
//using namespace helper;
//
//
//void wa() {
// printf("WA\n");
// exit(0);
//}
//
//bool check(const string& x) {
// if ((int)x.length() != n) {
// return false;
// }
// for (int i = 0; i < n; i++) {
// if (x[i] != '0' && x[i] != '1') {
// return false;
// }
// }
// return true;
//}
//
//void add_element(string x) {
// if (--w < 0 || compiled || !check(x)) {
// wa();
//
// }
// set_.insert(x);
//}
//
//bool check_element(string x) {
// if (--r < 0 || !compiled || !check(x)) {
// wa();
// }
// return set_.count(x);
//}
//int get_p(int i) {
// int ret = p[i];
// return ret;
//}
//
//void compile_set() {
// if (compiled) {
// wa();
// }
// compiled = true;
// set<string> compiledSet;
// string compiledElement = string(n, ' ');
// for (set<string>::iterator it = set_.begin(); it != set_.end(); it++) {
// string s = *it;
// for (int i = 0; i < n; i++) {
// compiledElement[i] = s[get_p(i)];
// }
// compiledSet.insert(compiledElement);
// }
// set_ = compiledSet;
//}
vector<int> restore_permutation(int n, int w, int r) {
function <void(int, int)> add = [&](int L, int R) {
if (L == R) return;
int mid = L + R >> 1;
string s(n, '1');
for (int i = L; i <= R; ++i) s[i] = '0';
// cout << L << ' ' << R << "aa\n";
for (int i = L; i <= mid; ++i) {
s[i] = '1';
add_element(s);
// cout << s << ' ' << L << ' ' << R << '\n';
s[i] = '0';
}
add(L, mid);
add(mid + 1, R);
};
add(0, n - 1);
// exit(0);
compile_set();
vector <int> ans(n);
function <void(int, int, vector <int>)> divide = [&](int L, int R, vector <int> p) {
if (L == R) {
assert(p.size() == 1);
ans[L] = p[0];
return;
}
int mid = L + R >> 1;
string s(n, '1');
vector <int> lft, rgt;
for (auto x: p) s[x] = '0';
for (auto x: p) {
s[x] = '1';
if (!check_element(s)) rgt.push_back(x);
else lft.push_back(x);
s[x] = '0';
}
divide(L, mid, lft);
divide(mid + 1, R, rgt);
};
vector <int> p;
for (int i = 0; i < n; ++i) p.push_back(i);
divide(0, n - 1, p);
return ans;
}
//
//
//// A convenience function.
//
//int main() {
// n = read_int();
// w = read_int();
// r = read_int();
// p = vector<int>(n);
// for (int i = 0; i < n; i++) {
// p[i] = read_int();
// }
// vector<int> answer = restore_permutation(n, w, r);
//
// if (answer.size() != n) {
// printf("WA\n");
// return 0;
// }
//
//
// printf("%d", answer[0]);
//
// for (int i = 1; i < n; i++) {
// printf(" %d", answer[i]);
// }
// printf("\n");
// return 0;
//}
컴파일 시 표준 에러 (stderr) 메시지
messy.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
2 | #pragma GCC optimization ("O3")
|
messy.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
3 | #pragma GCC optimization ("unroll-loops")
|
messy.cpp: In lambda function:
messy.cpp:92:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
92 | int mid = L + R >> 1;
| ~~^~~
messy.cpp: In lambda function:
messy.cpp:115:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
115 | int mid = L + R >> 1;
| ~~^~~
# | 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... |