Submission #606433

#	Time	Username	Problem	Language	Result	Execution time	Memory
606433		BJoozz	Shuffle (NOI19_shuffle)	C++14	67.55 / 100	236 ms	16336 KiB

shuffle

#include "shuffle.h"
#define X first
#define Y second
#define pb push_back
#include<bits/stdc++.h>
using namespace std;

//#define int long long
typedef pair < int , int > ii;
using ll = long long;
using ld = long double;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
int randint(int l,int r){
    return uniform_int_distribution < int > (l,r) (rng);
}
ld randld(ld l,ld r){
    return uniform_real_distribution <  > (l,r) (rng);
}
bool brand(int u,int v){
    return (uniform_int_distribution < int > (u,v) (rng) )<=u;
}

const int MAX=1000+5,inf=1e9,mod=1e9+7,base=311;

template <class X, class Y>
bool cmax(X &a, const Y &b) {
    return a < b ? a = b, 1 : 0;
}
template <class X, class Y>
bool cmin(X &a, const Y &b) {
    return a > b ? a = b, 1 : 0;
}
void maxx(ii &a,ii b){if(b>a)a=b;}
void minn(ii &a,ii b){if(b<a)a=b;}

void maxx(int &a,int b){if(b>a)a=b;}
void minn(int &a,int b){if(b<a)a=b;}
vector < vector < int > > V,T;
int n;
vector < int > vec,mem;

bitset < MAX > C[MAX],D;
int makenew(int B,int K){
    shuffle(vec.begin(),vec.end(),rng);
    int dem=0;
    for(int i=0;i<B;i++){
        D.reset();
        for(int j=0;j<K;j++)
        {
            V[i][j]=vec[i*K+j];
            dem+=(C[V[i][j]]&D).count();D[V[i][j]]=1;
        }
    }
    return dem;

}
void PL(ll &a,ll b){a+=b;if(a>=mod) a-=mod;}
ll P[MAX],FV[MAX],FT[MAX];
ll noV[MAX];
ll noT[MAX];
ll CV[MAX][MAX],CT[MAX][MAX];
//#undef int
vector<int> solve(int N, int B, int K, int Q, int ST)
//#define int long long
{
    n=N;
    for(int i=1;i<=N;i++)
        vec.pb(i);
    V.resize(B,vector < int > (K));
    int cn=n;
    ll temp=1;
    set < int > S;
    for(int i=1;i<=n;i++) C[i].set();
    for(int i=1;i<=n;i++) FV[i]=FT[i]=1;
    for(int z=1;z<=100;z++){
        temp=temp*base%mod;
        int M=n*n;
        for(int j=0;j<100;j++)if(cmin(M,makenew(B,K))) mem=vec;
        for(int i=0;i<B;i++){
            D.reset();
            for(int j=0;j<K;j++){
                V[i][j]=mem[i*K+j];
                D[V[i][j]]=1;
            }
            for(int u:V[i])C[u]&=D;
        }
        T=shuffle(V);
//        for(int u:mem) cout<<u<<' ';cout<<'\n';
//        for(int u:V[0]) cout<<u<<' ';cout<<'\n';
//        for(int u:T[0]) cout<<u<<' ';cout<<'\n';
        for(int i=0;i<B;i++){
            //P[++cn]=i;
            for(int u:T[i])for(int v:T[i])
                    PL(CT[u][v],temp);
            for(int u:V[i])for(int v:V[i])
                    PL(CV[u][v],temp);
        }
        for(int j=1;j<=n;j++)noV[j]=FV[j],noT[j]=FT[j];
        S.clear();
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                (FV[i]*=(noV[j]+CV[i][j]))%=mod;
                (FT[i]*=(noT[j]+CT[i][j]))%=mod;
//                cout<<FV[i]<<' '<<CV[i][j]<<'\n';;
            }
            S.insert(FV[i]);
        }
//        for(int i=1;i<=n;i++) cout<<FT[i]<<' ';cout<<'\n';
//        for(int i=1;i<=n;i++) cout<<FV[i]<<' ';cout<<'\n';
        //cerr<<z<<'\n';
        if(S.size()==n) break;
    }
    map < int , int > mp;
    for(int i=1;i<=n;i++)
        mp[FT[i]]=i;
        vector < int > ans;
    for(int i=1;i<=n;i++)ans.pb(mp[FV[i]]);
    //for(int u:ans) cout<<u<<' ';cout<<'\n';
    return ans;
}

Compilation message (stderr)

shuffle.cpp: In function 'std::vector<int> solve(int, int, int, int, int)':
shuffle.cpp:111:20: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  111 |         if(S.size()==n) break;
      |            ~~~~~~~~^~~
shuffle.cpp:114:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  114 |     for(int i=1;i<=n;i++)
      |     ^~~
shuffle.cpp:116:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  116 |         vector < int > ans;
      |         ^~~~~~
shuffle.cpp:70:9: warning: unused variable 'cn' [-Wunused-variable]
   70 |     int cn=n;
      |         ^~

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