| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 606462 |
2022-07-26T06:47:50 Z |
BJoozz |
Shuffle (NOI19_shuffle) |
C++14 |
|
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;
| ^~
| # |
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 |
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 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
77 ms |
15676 KB |
Wrong Answer. Used too many queries. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
246 ms |
16272 KB |
Wrong Answer. Used too many queries. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
