oj.uz

답안 #606433

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
606433 2022-07-26T06:43:27 Z BJoozz Shuffle (NOI19_shuffle) C++14
67.5544 / 100
 236 ms 16336 KB 
#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

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.0 / 2.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 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct

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 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 175 ms 16268 KB Output is correct
2 Correct 83 ms 11996 KB Output is correct
3 Correct 46 ms 5840 KB Output is correct
4 Correct 58 ms 6808 KB Output is correct
5 Correct 126 ms 16256 KB Output is correct

Subtask #4
0.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 81 ms 15752 KB Wrong Answer. Used too many queries.
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 236 ms 16244 KB Wrong Answer. Used too many queries.
2 Halted 0 ms 0 KB -

Subtask #6
50.5544318858 / 52.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 1236 KB Output is correct
2 Correct 25 ms 8288 KB Output is correct
3 Correct 55 ms 8220 KB Output is correct
4 Partially correct 177 ms 16260 KB Partially correct
5 Correct 80 ms 15316 KB Output is correct
6 Partially correct 216 ms 16224 KB Partially correct
7 Correct 69 ms 16116 KB Output is correct
8 Correct 26 ms 4028 KB Output is correct
9 Correct 58 ms 15308 KB Output is correct
10 Correct 42 ms 10188 KB Output is correct
11 Correct 125 ms 16336 KB Output is correct
12 Partially correct 183 ms 16216 KB Partially correct
13 Correct 109 ms 16300 KB Output is correct
14 Correct 84 ms 16324 KB Output is correct
15 Correct 34 ms 5380 KB Output is correct
16 Partially correct 204 ms 16268 KB Partially correct
17 Correct 4 ms 980 KB Output is correct
18 Partially correct 148 ms 14312 KB Partially correct
19 Correct 37 ms 5448 KB Output is correct
20 Correct 71 ms 15360 KB Output is correct