| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 606433 |
2022-07-26T06:43:27 Z |
BJoozz |
Shuffle (NOI19_shuffle) |
C++14 |
|
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;
| ^~
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
81 ms |
15752 KB |
Wrong Answer. Used too many queries. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
236 ms |
16244 KB |
Wrong Answer. Used too many queries. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
