oj.uz

답안 #545704

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
545704 2022-04-05T08:40:39 Z balbit Shuffle (NOI19_shuffle) C++14
56.0089 / 100
 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 | }
      | ^

Subtask #1
0.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 596 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
3.0 / 3.0

# 결과 실행 시간 메모리 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

Subtask #3
0.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 3 ms 1364 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
16.0 / 16.0

# 결과 실행 시간 메모리 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

Subtask #5
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 724 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
37.00892326 / 52.0

# 결과 실행 시간 메모리 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