Submission #1337270

#	Time	Username	Problem	Language	Result	Execution time	Memory
1337270		Luvidi	Shuffle (NOI19_shuffle)	C++20	51.14 / 100	1 ms	344 KiB

shuffle

#include "shuffle.h"
#include <bits/stdc++.h>
using namespace std;

#define pb push_back

vector<int> solve(int n, int b, int k, int q, int st) {
    int a[n+1];
    {   
        vector<vector<int>> v1(b);
        for(int i=1;i<=n;i++){
            v1[(i-1)/k].pb(i);
        }
        auto v2=shuffle(v1);
        for(int i=0;i<b;i++){
            for(int j=0;j<k;j++){
                a[v2[i][j]]=i;
            }
        }
        // for(int i=0;i<b;i++){
        //     cout<<i<<": ";
        //     for(int j=0;j<k;j++){
        //         cout<<v2[i][j]<<' ';
        //     }
        //     cout<<'\n';
        // }
    }
    int id[k];
    iota(id,id+k,0);
    id[k-1]+=-1+(id[k-2]&-id[k-2]);
    int nx[b],col[n+1];
    memset(col,0,sizeof(col));
    {   
        vector<vector<int>> v1(b);
        for(int i=0;i<b;i++){
            for(int j=0;j<k;j++){
                if(id[j]&1)v1[i].pb(i*k+j+1);
                else v1[(i+1)%b].pb(i*k+j+1);
            }
        }
        auto v2=shuffle(v1);
        for(int i=0;i<b;i++){
            map<int,int> m;
            for(int j=0;j<k;j++){
                m[a[v2[i][j]]]++;
            }
            vector<int> t;
            for(auto[x,y]:m)t.pb(x);
            if(m[t[1]]>m[t[0]])swap(t[0],t[1]);
            for(int j=0;j<k;j++){
                if(a[v2[i][j]]==t[1]){
                    col[v2[i][j]]^=1;
                }
            }
            nx[t[0]]=t[1];
        }
    }
    {   
        vector<vector<int>> v1(b);
        for(int i=0;i<2;i++){
            for(int j=0;j<k;j++){
                if(id[j]&1)v1[i].pb(i*k+j+1);
                else v1[!i].pb(i*k+j+1);
            }
        }
        for(int i=2;i<b;i++){
            for(int j=0;j<k;j++){
                v1[i].pb(i*k+j+1);
            }
        }
        auto v2=shuffle(v1);
        for(int i=0;i<b;i++){
            map<int,int> m;
            for(int j=0;j<k;j++){
                m[a[v2[i][j]]]++;
            }
            if(m.size()==1)continue;
            vector<int> t;
            for(auto[x,y]:m)t.pb(x);
            int x;
            if(nx[t[0]]==t[1])x=t[0];
            else x=t[1];
            t={x};
            for(int j=0;j<b-1;j++)t.pb(nx[t.back()]);
            int t2[b];
            for(int j=0;j<b;j++)t2[t[j]]=j;
            for(int j=1;j<=n;j++)a[j]=t2[a[j]];
            break;
        }
    }
    for(int z=1;(1<<z)<=id[k-1];z++){   
        vector<vector<int>> v1(b);
        for(int i=0;i<b;i++){
            for(int j=0;j<k;j++){
                if(id[j]>>z&1)v1[i].pb(i*k+j+1);
                else v1[(i+1)%b].pb(i*k+j+1);
            }
        }
        auto v2=shuffle(v1);
        for(int i=0;i<b;i++){
            map<int,int> m;
            for(int j=0;j<k;j++){
                m[a[v2[i][j]]]++;
            }
            vector<int> t;
            for(auto[x,y]:m)t.pb(x);
            if(m[t[1]]>m[t[0]])swap(t[0],t[1]);
            for(int j=0;j<k;j++){
                if(a[v2[i][j]]==t[1])col[v2[i][j]]^=1<<z;
            }
        }
    }
    map<int,int> id2;
    for(int i=0;i<k;i++)id2[id[i]]=i;
    vector<int> ans(n);
    for(int i=1;i<=n;i++){
        ans[a[i]*k+id2[col[i]]]=i;
    }
    return ans;
}

Compilation message (stderr)

grader.cpp: In function 'std::vector<std::vector<int> > shuffle(std::vector<std::vector<int> >)':
grader.cpp:51:51: warning: 'void std::random_shuffle(_RAIter, _RAIter, _Generator&&) [with _RAIter = __gnu_cxx::__normal_iterator<int*, vector<int> >; _Generator = int (&)(int)]' is deprecated: use 'std::shuffle' instead [-Wdeprecated-declarations]
   51 |         for (int i = 0; i < B; i++) random_shuffle(packed_cards[i].begin(), packed_cards[i].end(), myrandom);
      |                                     ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/13/algorithm:61,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51,
                 from grader.cpp:3:
/usr/include/c++/13/bits/stl_algo.h:4620:5: note: declared here
 4620 |     random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
      |     ^~~~~~~~~~~~~~
grader.cpp:52:36: warning: 'void std::random_shuffle(_RAIter, _RAIter, _Generator&&) [with _RAIter = __gnu_cxx::__normal_iterator<vector<int>*, vector<vector<int> > >; _Generator = int (&)(int)]' is deprecated: use 'std::shuffle' instead [-Wdeprecated-declarations]
   52 |         if (ST != 3) random_shuffle(packed_cards.begin(), packed_cards.end(), myrandom);
      |                      ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algo.h:4620:5: note: declared here
 4620 |     random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
      |     ^~~~~~~~~~~~~~

• Subtask 1: 2 / 2
• Subtask 2: 0 / 3
• Subtask 3: 0 / 12
• Subtask 4: 0 / 16
• Subtask 5: 0 / 15
• Subtask 6: 49.1446 / 52