Submission #1339801

#	Time	Username	Problem	Language	Result	Execution time	Memory
1339801		Luvidi	Shuffle (NOI19_shuffle)	C++20	19 / 100	1 ms	580 KiB

shuffle

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

#define pb push_back
#define pii pair<int,int>

const int maxn=2000;
vector<pii> ad[maxn+1];
bool vs[maxn+1];
bool cl[maxn+1];
vector<int> st;

void dfs(int v){
    vs[v]=1;
    for(auto[u,w]:ad[v])if(!vs[u]){
        cl[u]=!cl[v];
        dfs(u);
    }
}

void dfs2(int v,bool b){
    vs[v]=1;
    st.pb(v);
    for(auto[u,w]:ad[v])if(!vs[u]&&b==w){
        dfs2(u,!b);
    }
}

vector<int> solve(int n, int b, int k, int q, int ss) {
    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;
                ad[v2[i][j]].pb({v2[i][!j],0});
            }
        }
    }
    {
        vector<vector<int>> v1(b);
        for(int i=0;i<b;i++){
            v1[i].pb((i*k+1));
            v1[i].pb(((i+1)%b*k+2));
        }
        auto v2=shuffle(v1);
        for(int i=0;i<b;i++){
            for(int j=0;j<k;j++){
                ad[v2[i][j]].pb({v2[i][!j],1});
            }
        }
    }
    dfs(1);
    int cc[b];
    memset(cc,0,sizeof(cc));
    {   
        vector<vector<int>> v1(b);
        for(int i=1;i<=n;i++){
            v1[(i-1)/k].pb(i);
        }
        v1[0]={1,5};
        v1[1]={2,4};
        v1[2]={3,6};
        auto v2=shuffle(v1);
        for(int i=0;i<b;i++){
            int x=v2[i][0],y=v2[i][1];
            if(a[x]==a[y])continue;
            if(cl[x]==cl[y]){
                cc[a[x]]++;
                cc[a[y]]++;
            }
        }
    }
    int aa;
    {   
        vector<vector<int>> v1(b);
        for(int i=1;i<=n;i++){
            v1[(i-1)/k].pb(i);
        }
        v1[0]={1,4};
        v1[1]={2,6};
        v1[2]={3,5};
        auto v2=shuffle(v1);
        for(int i=0;i<b;i++){
            int x=v2[i][0],y=v2[i][1];
            if(a[x]==a[y])continue;
            if(cl[x]!=cl[y]){
                if(cc[a[x]]==2)aa=x;
                else aa=y;
            }
        }
    }
    memset(vs,0,sizeof(vs));
    dfs2(aa,1);
    rotate(st.begin(),st.end()-1,st.end());
    for(int i=0;i<n;i+=2)swap(st[i],st[i+1]);
    return st;
}

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: 0 / 2
• Subtask 2: 3 / 3
• Subtask 3: 0 / 12
• Subtask 4: 16 / 16
• Subtask 5: 0 / 15
• Subtask 6: 0 / 52