#include <bits/stdc++.h>
#include "messy.h"
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define MASK(i) (1ULL << (i))
#define GETBIT(mask, i) (((mask) >> (i)) & 1)
#define ALL(v) (v).begin(), (v).end()
ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
ll LASTBIT(ll mask){return (mask) & (-mask);}
int pop_cnt(ll mask){return __builtin_popcountll(mask);}
int ctz(ull mask){return __builtin_ctzll(mask);}
int logOf(ull mask){return 63 - __builtin_clzll(mask);}
// mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
mt19937_64 rng(20);
ll rngesus(ll l, ll r){return l + (ull) rng() % (r - l + 1);}
template <class T1, class T2>
bool maximize(T1 &a, T2 b){
if (a < b) {a = b; return true;}
return false;
}
template <class T1, class T2>
bool minimize(T1 &a, T2 b){
if (a > b) {a = b; return true;}
return false;
}
template <class T>
void printArr(T& container, string separator = " ", string finish = "\n", ostream &out = cout){
for(auto item: container) out << item << separator;
out << finish;
}
template <class T>
void remove_dup(vector<T> &a){
sort(ALL(a));
a.resize(unique(ALL(a)) - a.begin());
}
// const int INF = 2e9 + 69;
// namespace Interactor{
// int n;
// vector<int> perm;
// vector<string> S;
// int w_cnt, r_cnt;
// void add_element(string s){
// // cout << "Add: " << s << "\n";
// S.push_back(s);
// w_cnt++;
// }
// void compile_set(){
// for(string &s: S){
// string t(n, '0');
// for(int i= 0; i<n; ++i) t[i] = s[perm[i]];
// s = t;
// }
// sort(ALL(S));
// }
// bool check_element(string s){
// // cout << "Query: " << s << "\n";
// r_cnt++;
// return binary_search(ALL(S), s);
// }
void send_nude(int n){
add_element("1" + string(n-1, '0'));
add_element("10" + string(n-2, '1'));
for(int i = 0; MASK(i) < n; ++i){
string cur = string(n, '0');
cur[0] = '1';
cur[MASK(i)] = '1';
add_element(cur);
cur[MASK(i)] = '0';
}
for(int i = 1; MASK(i) < n; ++i){
string cur = string(n, '0'); cur[0] = '1';
for(int j = 0; j <= i; ++j) cur[MASK(j)] = '1';
add_element(cur);
}
for(int i = 1; i<n; ++i) if (i != LASTBIT(i)){
string cur(n, '0'); cur[i] = '1';
for(int j = 0; MASK(j) < n; ++j) if (GETBIT(i, j)) {
cur[MASK(j)] = '1';
add_element(cur);
cur[MASK(j)] = '0';
}
}
}
vector<int> find_happiness(int n){
vector<int> ans(n, -1), perm(n);
for(int i = 0; i<n; ++i) perm[i] = i;
shuffle(ALL(perm), rng);
int zeroPos = -1;
for(int i: perm){
string cur(n, '0');
cur[i] = '1';
if (check_element(cur)){
zeroPos = i;
break;
}
}
vector<int> PowerOfTwo;
for(int i: perm) if (i != zeroPos){
string cur(n, '0');
cur[zeroPos] = cur[i] = '1';
if (check_element(cur)){
PowerOfTwo.push_back(i);
}
if (MASK(PowerOfTwo.size()) == n) break;
}
vector<int> PowerTower;
for(int j = 0; j < PowerOfTwo.size(); ++j){
int i = PowerOfTwo[j];
string cur(n, '1');
cur[i] = '0';
if (check_element(cur)) {
PowerTower.push_back(i);
PowerOfTwo.erase(PowerOfTwo.begin() + j);
break;
}
}
while(PowerOfTwo.size()){
for(int j = 0; j < PowerOfTwo.size(); ++j){
int i = PowerOfTwo[j];
string cur(n, '0');
cur[zeroPos] = cur[i] = '1';
for(int i: PowerTower) cur[i] = '1';
if (check_element(cur)) {
PowerTower.push_back(i);
PowerOfTwo.erase(PowerOfTwo.begin() + j);
break;
}
}
}
ans[zeroPos] = 0;
for(int i= 0; i<PowerTower.size(); ++i) ans[PowerTower[i]] = MASK(i);
vector<int> signature(n);
int m = PowerTower.size();
for(int i = 0; i<PowerTower.size(); ++i){
vector<pair<int, int>> cnt(MASK(i), {0, 0});
for(int j = 0; j<n; ++j) if (j != 0 && LASTBIT(j) != j){
int k = j & (MASK(i) - 1);
if (GETBIT(j, i)) cnt[k].second++;
else cnt[k].first++;
}
for(int j: perm) if (ans[j] == -1){
if (cnt[signature[j]].second == 0){
cnt[signature[j]].first--;
continue;
}
if (cnt[signature[j]].first == 0){
cnt[signature[j]].second--;
signature[j] += MASK(i);
continue;
}
string cur(n, '0');
cur[PowerTower[i]] = cur[j] = '1';
if (check_element(cur)){
cnt[signature[j]].second--;
signature[j] += MASK(i);
}
else cnt[signature[j]].first--;
}
}
for(int i = 0; i<n; ++i) if (ans[i] == -1) ans[i] = signature[i];
return ans;
}
vector<int> restore_permutation(int n, int w, int r) {
send_nude(n);
compile_set();
return find_happiness(n);
}
// bool solve(int _n, vector<int> _perm){
// n = _n; perm = _perm;
// w_cnt = r_cnt = 0;
// return restore_permutation(n, 1000, 1000) == perm;
// }
// void resource_hog(){
// cout << "Write cnt: " << w_cnt << "\n";
// cout << "Read cnt: " << r_cnt << "\n";
// }
// }
// int main(void){
// ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// int n; cin >> n;
// vector<int> perm(n);
// for(int i = 0; i<n; ++i) perm[i] = i;
// shuffle(ALL(perm), rng);
// bool verdict = Interactor::solve(n, perm);
// if (verdict) cout << "AC\n";
// else cout << "WA\n";
// Interactor::resource_hog();
// return 0;
// }
Compilation message
messy.cpp: In function 'void send_nude(int)':
messy.cpp:82:32: warning: comparison of integer expressions of different signedness: 'long long unsigned int' and 'int' [-Wsign-compare]
82 | for(int i = 0; MASK(i) < n; ++i){
| ^
messy.cpp:89:32: warning: comparison of integer expressions of different signedness: 'long long unsigned int' and 'int' [-Wsign-compare]
89 | for(int i = 1; MASK(i) < n; ++i){
| ^
messy.cpp:96:36: warning: comparison of integer expressions of different signedness: 'long long unsigned int' and 'int' [-Wsign-compare]
96 | for(int j = 0; MASK(j) < n; ++j) if (GETBIT(i, j)) {
| ^
messy.cpp: In function 'std::vector<int> find_happiness(int)':
messy.cpp:125:41: warning: comparison of integer expressions of different signedness: 'long long unsigned int' and 'int' [-Wsign-compare]
125 | if (MASK(PowerOfTwo.size()) == n) break;
| ^
messy.cpp:129:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
129 | for(int j = 0; j < PowerOfTwo.size(); ++j){
| ~~^~~~~~~~~~~~~~~~~~~
messy.cpp:141:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
141 | for(int j = 0; j < PowerOfTwo.size(); ++j){
| ~~^~~~~~~~~~~~~~~~~~~
messy.cpp:155:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
155 | for(int i= 0; i<PowerTower.size(); ++i) ans[PowerTower[i]] = MASK(i);
| ~^~~~~~~~~~~~~~~~~~
messy.cpp:158:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
158 | for(int i = 0; i<PowerTower.size(); ++i){
| ~^~~~~~~~~~~~~~~~~~
messy.cpp:157:13: warning: unused variable 'm' [-Wunused-variable]
157 | int m = PowerTower.size();
| ^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
344 KB |
n = 8 |
2 |
Correct |
1 ms |
348 KB |
n = 8 |
3 |
Correct |
0 ms |
348 KB |
n = 8 |
4 |
Correct |
0 ms |
344 KB |
n = 8 |
5 |
Correct |
0 ms |
348 KB |
n = 8 |
6 |
Correct |
0 ms |
348 KB |
n = 8 |
7 |
Correct |
0 ms |
348 KB |
n = 8 |
8 |
Correct |
0 ms |
348 KB |
n = 8 |
9 |
Correct |
0 ms |
348 KB |
n = 8 |
10 |
Correct |
1 ms |
348 KB |
n = 8 |
11 |
Correct |
0 ms |
348 KB |
n = 8 |
12 |
Correct |
0 ms |
348 KB |
n = 8 |
13 |
Correct |
0 ms |
348 KB |
n = 8 |
14 |
Correct |
0 ms |
348 KB |
n = 8 |
15 |
Correct |
1 ms |
440 KB |
n = 8 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
n = 32 |
2 |
Correct |
0 ms |
348 KB |
n = 32 |
3 |
Correct |
1 ms |
348 KB |
n = 32 |
4 |
Correct |
1 ms |
348 KB |
n = 32 |
5 |
Correct |
1 ms |
348 KB |
n = 32 |
6 |
Correct |
0 ms |
348 KB |
n = 32 |
7 |
Correct |
0 ms |
348 KB |
n = 32 |
8 |
Correct |
0 ms |
348 KB |
n = 32 |
9 |
Correct |
0 ms |
344 KB |
n = 32 |
10 |
Correct |
0 ms |
348 KB |
n = 32 |
11 |
Correct |
1 ms |
348 KB |
n = 32 |
12 |
Correct |
1 ms |
348 KB |
n = 32 |
13 |
Correct |
0 ms |
348 KB |
n = 32 |
14 |
Correct |
1 ms |
348 KB |
n = 32 |
15 |
Correct |
0 ms |
348 KB |
n = 32 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
344 KB |
n = 32 |
2 |
Correct |
1 ms |
344 KB |
n = 32 |
3 |
Correct |
1 ms |
348 KB |
n = 32 |
4 |
Correct |
0 ms |
348 KB |
n = 32 |
5 |
Correct |
1 ms |
440 KB |
n = 32 |
6 |
Correct |
0 ms |
344 KB |
n = 32 |
7 |
Correct |
0 ms |
348 KB |
n = 32 |
8 |
Correct |
0 ms |
348 KB |
n = 32 |
9 |
Correct |
1 ms |
344 KB |
n = 32 |
10 |
Correct |
1 ms |
348 KB |
n = 32 |
11 |
Correct |
1 ms |
408 KB |
n = 32 |
12 |
Correct |
1 ms |
348 KB |
n = 32 |
13 |
Correct |
0 ms |
348 KB |
n = 32 |
14 |
Correct |
1 ms |
348 KB |
n = 32 |
15 |
Correct |
0 ms |
348 KB |
n = 32 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
604 KB |
n = 128 |
2 |
Correct |
1 ms |
856 KB |
n = 128 |
3 |
Correct |
1 ms |
604 KB |
n = 128 |
4 |
Correct |
1 ms |
604 KB |
n = 128 |
5 |
Correct |
1 ms |
604 KB |
n = 128 |
6 |
Correct |
1 ms |
604 KB |
n = 128 |
7 |
Correct |
1 ms |
604 KB |
n = 128 |
8 |
Correct |
1 ms |
604 KB |
n = 128 |
9 |
Correct |
1 ms |
604 KB |
n = 128 |
10 |
Correct |
1 ms |
604 KB |
n = 128 |
11 |
Correct |
1 ms |
604 KB |
n = 128 |
12 |
Correct |
2 ms |
604 KB |
n = 128 |
13 |
Correct |
1 ms |
440 KB |
n = 128 |
14 |
Correct |
1 ms |
604 KB |
n = 128 |
15 |
Correct |
1 ms |
604 KB |
n = 128 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
600 KB |
n = 128 |
2 |
Correct |
1 ms |
600 KB |
n = 128 |
3 |
Correct |
1 ms |
640 KB |
n = 128 |
4 |
Correct |
1 ms |
604 KB |
n = 128 |
5 |
Incorrect |
1 ms |
604 KB |
grader returned WA |
6 |
Halted |
0 ms |
0 KB |
- |