oj.uz

답안 #606462

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
606462 2022-07-26T06:47:50 Z BJoozz Shuffle (NOI19_shuffle) C++14
67.5544 / 100
 246 ms 16472 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) {
    if(a==b) return randint(0,1);
    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;
        //if(z==2) for(int j=0;j<10;j++)cout<<makenew(B,K)<<'\n';
        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:114:20: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  114 |         if(S.size()==n) break;
      |            ~~~~~~~~^~~
shuffle.cpp:118:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  118 |     for(int i=1;i<=n;i++)
      |     ^~~
shuffle.cpp:120:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  120 |         vector < int > ans;
      |         ^~~~~~
shuffle.cpp:71:9: warning: unused variable 'cn' [-Wunused-variable]
   71 |     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 176 ms 16232 KB Output is correct
2 Correct 83 ms 11860 KB Output is correct
3 Correct 45 ms 5880 KB Output is correct
4 Correct 46 ms 6800 KB Output is correct
5 Correct 140 ms 16284 KB Output is correct

Subtask #4
0.0 / 16.0

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

Subtask #5
0.0 / 15.0

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

Subtask #6
50.5544318858 / 52.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 1236 KB Output is correct
2 Correct 30 ms 8220 KB Output is correct
3 Correct 59 ms 8220 KB Output is correct
4 Partially correct 170 ms 16472 KB Partially correct
5 Correct 80 ms 15256 KB Output is correct
6 Partially correct 176 ms 16368 KB Partially correct
7 Correct 60 ms 16084 KB Output is correct
8 Correct 29 ms 4028 KB Output is correct
9 Correct 56 ms 15232 KB Output is correct
10 Correct 40 ms 10312 KB Output is correct
11 Correct 103 ms 16296 KB Output is correct
12 Partially correct 176 ms 16360 KB Partially correct
13 Correct 101 ms 16308 KB Output is correct
14 Correct 62 ms 16312 KB Output is correct
15 Correct 34 ms 5376 KB Output is correct
16 Partially correct 172 ms 16236 KB Partially correct
17 Correct 4 ms 980 KB Output is correct
18 Partially correct 158 ms 14488 KB Partially correct
19 Correct 33 ms 5460 KB Output is correct
20 Correct 70 ms 15352 KB Output is correct