Submission #545676

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
545676	2022-04-05T07:10:50 Z	balbit	Shuffle (NOI19_shuffle)	C++14	14 / 100	31 ms	25136 KB

shuffle

#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 = 3e5+5;

#define VI vector<int>

#ifdef BALBIT

vector<int> per = {1,4,2,3,6,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]));
    }
    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;
    return gt;
}

vector<int> solve(int N, int B, int K, int Q, int ST) {

    auto F = [&](int &at) {int oat = at; at = (at+1)%B; return oat; };

    if (ST == 3) {
        // shuffle solving for the case where the buckets AREN't shuffled
        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 = myshuffle(ask);

            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;
    }

}



//signed main(){
//    ios::sync_with_stdio(0), cin.tie(0);
//    bug(1,2);
//    vector<int> gt = solve(6,2,3,-1,3);
//    for(int x : gt) cout<<x<<' ';
//    cout<<endl;
//}

Compilation message

shuffle.cpp: In function 'std::vector<int> solve(int, int, int, int, int)':
shuffle.cpp:16:18: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   16 | #define REP(i,n) for (int i = 0; i<n; ++i)
      |                  ^~~
shuffle.cpp:72:9: note: in expansion of macro 'REP'
   72 |         REP(i,N) strt.pb(i); v.pb({strt, strt});
      |         ^~~
shuffle.cpp:72:30: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   72 |         REP(i,N) strt.pb(i); v.pb({strt, strt});
      |                              ^
shuffle.cpp:131:1: warning: control reaches end of non-void function [-Wreturn-type]
  131 | }
      | ^

Subtask #1
2.0 / 2.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	312 KB	Output is correct
3	Correct	0 ms	308 KB	Output is correct
4	Correct	0 ms	308 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct

Subtask #2
0.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	1 ms	340 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-

Subtask #3
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	696 KB	Output is correct
2	Correct	9 ms	13012 KB	Output is correct
3	Correct	3 ms	4308 KB	Output is correct
4	Correct	1 ms	468 KB	Output is correct
5	Correct	20 ms	24020 KB	Output is correct