#include "messy.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define all( x ) x.begin(), x.end()
#define umin( x, y ) x = min( x, (y) )
#define umax( x, y ) x = max( x, (y) )
using namespace std;
typedef long long Lint;
typedef pair<int,int> ii;
const int maxn = 220;
int n;
vector<int> ans;
vector<int> known;
int kn[maxn];
map<string,int> mp;
set<int> st[maxn];
int num( string s ) {
int ret = 0;
for(int i=0;i<s.size();i++) if( s[i] == '1' ) ret++;
return ret;
}
void add( int x, int k, int t ) {
string s = "";
for(int i=0;i<n;i++) s += !k + '0';
for(int i=0;i<known.size();i++)
s[known[i]] = '0' + k;
s[x] = k + '0';
if( num( s ) != t || mp.count( s ) ) return;
mp[s] = 1;
//cout << "added " << s << endl;
add_element( s );
}
bool check( int x, int k, int t ) {
string s = "";
for(int i=0;i<n;i++) s += !k + '0';
for(int i=0;i<known.size();i++)
s[known[i]] = '0' + k;
s[x] = k + '0';
if( num( s ) != t ) return false;
assert( mp.count(s) == 0 );
mp[s] = 1;
//cout << "checked " << s << endl;
for(int i=0;i<300;i++) check_element( s );
return check_element( s );
}
vector<int> restore_permutation(int N, int w, int r) {
n = N;
ans.resize( n );
for(int i=1;(1<<i)<=n;i++) {
add( i-1, 0, n-i );
int h = n / (1<<i);
for(int j=0;j<n;j++)
if( (j/h)%2 == 0 ) add( j, 1, i );
known.pb( i-1 );
}
compile_set();
known.clear();
mp.clear();
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
st[i].insert( j );
for(int i=1;(1<<i)<=n;i++) {
int loc = -1;
for(int j=0;j<n;j++)
if( check( j, 0, n-i ) ) {
loc = j;
break;
}
assert( loc >= 0 );
ans[i-1] = loc;
for(int j=i;j<n;j++)
st[j].erase( loc );
int h = n / (1<<i);
vector<int> v1, v0;
for(int j=0;j<n;j++) {
if( check( j, 1, i ) ) {
v1.pb( j );
} else v0.pb( j );
}
for(int j=0;j<n;j++) {
if( (j/h)%2 == 0 ) {
for(int k=0;k<v0.size();k++)
st[j].erase( v0[k] );
} else {
for(int k=0;k<v1.size();k++)
st[j].erase( v1[k] );
}
}
known.pb( loc );
kn[loc] = 1;
}
for(int i=0;i<n;i++) {
if( (1<<i) < n ) continue;
assert( st[i].size() == 1 );
ans[i] = *st[i].begin();
}
vector<int> re(n);
for(int i=0;i<n;i++) re[ ans[i] ] = i;
return re;
}
Compilation message
messy.cpp: In function 'int num(std::__cxx11::string)':
messy.cpp:26:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<s.size();i++) if( s[i] == '1' ) ret++;
~^~~~~~~~~
messy.cpp: In function 'void add(int, int, int)':
messy.cpp:33:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<known.size();i++)
~^~~~~~~~~~~~~
messy.cpp: In function 'bool check(int, int, int)':
messy.cpp:45:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<known.size();i++)
~^~~~~~~~~~~~~
messy.cpp: In function 'std::vector<int> restore_permutation(int, int, int)':
messy.cpp:100:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int k=0;k<v0.size();k++)
~^~~~~~~~~~
messy.cpp:103:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int k=0;k<v1.size();k++)
~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
grader returned WA |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
grader returned WA |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
grader returned WA |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
1152 KB |
grader returned WA |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
1152 KB |
grader returned WA |
| 2 |
Halted |
0 ms |
0 KB |
- |
