| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 545704 |
2022-04-05T08:40:39 Z |
balbit |
Shuffle (NOI19_shuffle) |
C++14 |
|
12 ms |
16264 KB |
#include "shuffle.h"
#include <bits/stdc++.h>
//#define int ll
using namespace std;
#define ll long long
#define f first
#define s second
#define pii pair<int, int>
#define MX(a,b) a=max(a,b)
#define MN(a,b) a=min(a,b)
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(), (x).end()
#define REP(i,n) for (int i = 0; i<n; ++i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
#define pb push_back
#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<": "<<#__VA_ARGS__<<"- ", _do(__VA_ARGS__)
template<typename T> void _do( T && x) {cerr<<x<<endl;}
template<typename T, typename ...S> void _do( T && x, S && ...y) {cerr<<x<<", "; _do(y...);}
#else
#define bug(...)
#define endl '\n'
#endif // BALBIT
const int maxn = 1e3+5;
#define VI vector<int>
#ifdef BALBIT
vector<int> per = {4,3,9,8,6,1,7,2,5};
std::vector< std::vector<int> > shuffle(std::vector< std::vector<int> > x){
REP(i, SZ(x)) {
for (int &y:x[i]) {
y = per[y-1];
}
random_shuffle(ALL(x[i]));
}
random_shuffle(ALL(x));
return x;
// REP(i, SZ(x)) {
// for (int y : x[i]) cout<<y<<' ';
// cout<<endl;
// }
// cout<<endl;
// bug("enter!");
// vector<vector<int> > re(SZ(x), vector<int> (SZ(x[0])));
// REP(i, SZ(x)) REP(j, SZ(x[0])) cin>>x[i][j];
// return re;
}
#endif // BALBIT
vector<vector<int> > myshuffle(vector<vector<int> > b) {
for (auto &y : b) for (int &x : y) ++x;
vector<vector<int> > gt = shuffle(b);
for (auto &y : gt) {
for(int &x : y) --x;
sort(ALL(y));
}
return gt;
}
vector<int> g[maxn]; // the induced graph from the buckets
bool seen[maxn];
vector<int> ord2;
void dfs2(int v) {
seen[v] =1;
ord2.pb(v);
for (int u : g[v]) {
if (!seen[u]) {
dfs2(u);
}
}
}
vector<vector<int> > cleanshuffle(vector<vector<int> > ask, int N, int B, int K) {
vector<vector<int> > gt = myshuffle(ask);
vector<int> color(N); // which bucket is this number in in the original
REP(i, B) {
for (int x : gt[i]) color[x] = i;
}
// now time to make a loop
vector<vector<int> > ask2 = ask;
REP(i, B) {
ask2[i][0] = ask[(i-1+B)%B][0];
}
vector<vector<int> > gt2 = myshuffle(ask2);
// ok now i can find the chain
REP(i,B) {
g[i].clear();
}
REP(i, B) {
// the type that appears the least number of times is the poker
map<int, int> mp;
for (int t : gt2[i]) {
mp[color[t]]++;
}
assert(SZ(mp) == 2);
vector<int> here;
for (pii p :mp) {
here.pb(p.f);
}
for (pii p : mp) {
if (p.s == 1) {
// found you
int oth = here[0] ^ here[1] ^ p.f;
g[p.f].pb(oth); // Color edge corresponds to index(i) -> index(i+1)
}
}
}
// now i just need to find the node of index 0
memset(seen, 0, sizeof seen);
vector<vector<int> > ask3 = ask;
swap(ask3[0][0], ask3[1][0]);
swap(ask3[0][1], ask3[2][0]);
// now 2 of index 0s are scattered in other zones, so wee look for the color with 2 scattered locations
// (should be unique)
vector<vector<int> > gt3 = myshuffle(ask3);
map<int, int> funny;
REP(i, B) {
// the type that appears the least number of times is the poker
map<int, int> mp;
for (int t : gt3[i]) {
mp[color[t]]++;
}
vector<int> here;
int mostfreq = 0;
for (pii p :mp) {
MX(mostfreq, p.s);
}
for (pii p : mp) {
if (p.s != mostfreq) {
funny[p.f]++;
}
}
}
int one = -1;
for (pii p:funny) {
if (p.s == 2) {
assert(one == -1);
one = p.f;
}
}
assert(one != -1);
ord2.clear();
dfs2(one);
vector<vector<int> > ret;
for (int x : ord2) {
ret.pb(gt[x]);
}
return ret;
}
vector<int> g1[maxn], g2[maxn];
vector<int> ord;
void dfs(int v, bool one) {
ord.pb(v); seen[v] = 1;
for (int u : (one?g1:g2)[v]) {
if (!seen[u]) {
dfs(u, one^1);
}
}
}
#define vvi vector<vector<int> >
vector<int> chg(vvi a, vvi b) {
vector<int> GP(SZ(a) * SZ(a[0]));
REP(i, SZ(a)) {
for (int x : a[i]) {
GP[x] = i;
}
}
vector<int> re;
REP(i, SZ(b)) {
for (int x : b[i]) {
if (i != GP[x]) {
re.pb(x);
}
}
}
return re;
}
void ASS(bool t) {
if (!t) {
while(1);
}
}
vector<int> run(int N, int B, int K, int Q, bool isclean){
// shuffle solving for the case where the buckets AREN't shuffled
auto F = [&](int &at) {int oat = at; at = (at+1)%B; return oat; };
vector<pair<VI, VI> > v;
vector<int> strt;
REP(i,N) strt.pb(i);
v.pb({strt, strt});
// groups of {index, p[i]}
while (1) {
vector<vector<int> > ask (B);
vector<int> whichbucket(N); // which bucket is this index tossed into?
vector<int> group(N); // which group is this result from?
bool need = 0;
int AT = 0;
int grp = 0;
vector<vector<pair<VI, VI> > > yeah(SZ(v));
for (auto &e : v) {
yeah[grp].resize(B);
if (SZ(e.f) > 1) need = 1;
REP(i, SZ(e.f)) {
whichbucket[e.f[i]] = AT;
yeah[grp][AT].f.pb(e.f[i]);
ask[AT].pb(e.f[i]);
F(AT);
}
for (int x : e.s) {
group[x]=grp;
}
++grp;
}
if (need == 0) break;
vector<vector<int> > get = (isclean?myshuffle(ask) : cleanshuffle(ask,N,B,K));
vector<pair<VI, VI> > nv;
REP(i, B) {
REP(j, K) {
yeah[group[get[i][j]]][i].s.pb(
get[i][j]);
}
}
for (auto & e : yeah) {
REP(i,B) {
if (SZ(e[i].f)) {
nv.pb(e[i]);
}
}
}
v.swap(nv);
}
vector<int> re(N);
bug(SZ(v));
assert(SZ(v) == N);
REP(i, SZ(v)) {
re[v[i].f[0]] = v[i].s[0] + 1;
}
return re;
}
vector<int> solve(int N, int B, int K, int Q, int ST) {
if (ST == 3 || ST == 1) {
run(N,B,K,Q,1);
}
else if (ST == 4 || ST == 2) {
assert(K == 2);
vector<vector<int> > ask1, ask2;
REP(i,N) {
if (i % 2 == 0) {
ask1.pb({i, i+1});
}else{
ask2.pb({i, (i+1)%N});
}
}
vector<vector<int> > gt1 = myshuffle(ask1), gt2 = myshuffle(ask2);
sort(ALL(gt1)); sort(ALL(gt2));
// build graphs
REP(i,SZ(gt1)) {
g1[gt1[i][0]].pb(gt1[i][1]);
g1[gt1[i][1]].pb(gt1[i][0]);
g2[gt2[i][0]].pb(gt2[i][1]);
g2[gt2[i][1]].pb(gt2[i][0]);
}
swap(ask1[0][0], ask1[1][0]); // swapping 0 and 2 (1 and 3 in 1-based)
vector<vector<int> > c1 = myshuffle(ask1);
swap(ask1[0][0], ask1[1][0]);
// now look for the pair that doesn't appear in either ask1 or ask2: that is the sus pair
vector<int> d1;
for (vector<int> t : c1) {
if (!binary_search(ALL(gt1), t) && !binary_search(ALL(gt2), t)) {
bug(t[0], t[1]);
assert(SZ(d1) == 0);
d1 = t;
}
}
swap(ask1[0][0], ask1[2][1]);
vector<vector<int> > c2 = myshuffle(ask1);
swap(ask1[0][0], ask1[2][1]);
vector<int> d2;
for (vector<int> t : c2) {
if (!binary_search(ALL(gt1), t) && !binary_search(ALL(gt2), t)) {
// assert(SZ(d2) == 0);
// d2 = t;
for (int y : t) d2.pb(y);
}
}
bug(SZ(d1), SZ(d2));
ASS(SZ(d1) == 2); // ASS(SZ(d2) == 2);
int one = -1;
for (int x : d1) for (int y : d2) if (x == y) one = x;
ASS(one != -1);
dfs(one, 1);
for (int &x : ord) ++x;
return ord;
}
else if (ST == 6) {
// try to steal 3 but with weird voodoo to unrandomize the buckets
return run(N,B,K,Q,0);
}
}
#ifdef BALBIT
signed main(){
ios::sync_with_stdio(0), cin.tie(0);
bug(1,2);
vector<int> gt = solve(9,3,3,-1,6);
for(int x : gt) cout<<x<<' ';
cout<<endl;
}
#endif
Compilation message
shuffle.cpp: In function 'std::vector<int> solve(int, int, int, int, int)':
shuffle.cpp:345:1: warning: control reaches end of non-void function [-Wreturn-type]
345 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
596 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
384 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
1364 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
724 KB |
Output is correct |
| 2 |
Correct |
1 ms |
468 KB |
Output is correct |
| 3 |
Correct |
1 ms |
468 KB |
Output is correct |
| 4 |
Correct |
1 ms |
468 KB |
Output is correct |
| 5 |
Correct |
2 ms |
596 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
724 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
1 ms |
388 KB |
Partially correct |
| 2 |
Correct |
2 ms |
1492 KB |
Output is correct |
| 3 |
Partially correct |
2 ms |
468 KB |
Partially correct |
| 4 |
Partially correct |
5 ms |
724 KB |
Partially correct |
| 5 |
Correct |
5 ms |
5632 KB |
Output is correct |
| 6 |
Partially correct |
4 ms |
724 KB |
Partially correct |
| 7 |
Correct |
3 ms |
2644 KB |
Output is correct |
| 8 |
Partially correct |
1 ms |
468 KB |
Partially correct |
| 9 |
Correct |
3 ms |
3668 KB |
Output is correct |
| 10 |
Correct |
3 ms |
3028 KB |
Output is correct |
| 11 |
Correct |
12 ms |
16212 KB |
Output is correct |
| 12 |
Partially correct |
4 ms |
768 KB |
Partially correct |
| 13 |
Correct |
12 ms |
16264 KB |
Output is correct |
| 14 |
Correct |
3 ms |
2388 KB |
Output is correct |
| 15 |
Partially correct |
2 ms |
468 KB |
Partially correct |
| 16 |
Partially correct |
4 ms |
724 KB |
Partially correct |
| 17 |
Partially correct |
1 ms |
340 KB |
Partially correct |
| 18 |
Partially correct |
4 ms |
768 KB |
Partially correct |
| 19 |
Partially correct |
2 ms |
512 KB |
Partially correct |
| 20 |
Correct |
6 ms |
7556 KB |
Output is correct |
