# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
993951 | Lib | Magic Show (APIO24_show) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
//#include "Alice.h"
using namespace std;
int toggled[500];
int perm1[10000];
int perm2[10000];
int perm3[10000];
long long x;
long long len=4801;
set <int> rem;
vector <pair<int,int> > TVector;
vector <vector<int> > inGroup;
vector <pair<int,int> > TVector2;
vector <int> nums;
/*
long long setN(int n){
return 177013;
}*/
vector<pair <int,int>> Alice(){
setN(x);
x=177013;
x^=463222221001217544;
//cout<<x<<"\n";
int toggledcnt=0;
inGroup.clear();
TVector.clear();
for(int i=1;i<=200;i++){
inGroup.push_back(nums);
}
for(int i=0;i<=60;i++){
if(x >> i & 1){
toggled[i]=1;
toggledcnt++;
}
}
for(int i=1;i<=4801;i++){
perm1[i]=-1;
rem.insert(i);
inGroup[(i-1)/34].push_back(i);
}
//initialize the 1st perm;
for(int i=0;i<=60;i++){
if(toggled[i]){
for(int k=1;k<=17;k++){
perm1[i*17+k]=i;
}
for(int k=1;k<=34;k++){
rem.erase(i*34+k);
}
}
}
srand(123190);
for(int i=1;i<=len-1-toggledcnt*17;i++){
swap(perm1[i],perm1[rand()%(len-i-toggledcnt*17)+i]);
}
for(int i=1;i<=len-toggledcnt*17;i++){
//cout<<perm1[i]<<" ";
}
int cur=1,cur2=1,cur3=1;
for(int i=1;i<=4801;i++){
if(rem.count(i)){
perm3[cur]=i;
cur++;
}
}
int ta,tb;
for(int i=0;i<=60;i++){
for(int k=1;k<=500;k++){
ta=rand()%34;
tb=rand()%34;
swap(inGroup[i][ta],inGroup[i][tb]);
}
for(int k=0;k<34;k++){
// cout<<inGroup[i][k]<<" ";
}
}
cur--;
for(int i=2;i<cur;i++){
swap(perm3[i],perm3[rand()%(cur-i)+i+1]);
ta=(perm3[i]-1)/34;
tb=(perm3[i-1]-1)/34;
while(ta==tb&&(!toggled[ta]||ta>60)){
swap(perm3[i],perm3[rand()%(cur-i)+i+1]);
ta=(perm3[i]-1)/34;
tb=(perm3[i-1]-1)/34;
}
}
cur=1;
for(int i=1;i<=len-toggledcnt*17;i++){
if(perm1[i]>-1){
perm2[cur]=inGroup[perm1[i]].back();
inGroup[perm1[i]].pop_back();
perm2[cur+1]=inGroup[perm1[i]].back();
inGroup[perm1[i]].pop_back();
cur+=2;
}else{
perm2[cur]=perm3[cur2];
cur2++;
cur++;
}
}
for(int i=1;i<=4800;i++){
// cout<<perm2[i]<<" ";
TVector.push_back({perm2[i],perm2[i+1]});
}
for(int i=0;i<=60;i++){
if(toggled[i]){
// cout<<i<<" ";
}
}
//cout<<"\n";
return TVector;
}
/*
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout<<(177013^463222221001217544)<<"\n";
cout<<x<<"\n";
TVector2=Alice();
for(int i=0;i<4800;i++){
// cout<<TVector2[i].first<<" "<<TVector2[i].second<<"\n";
}
}*/
#include <bits/stdc++.h>
//#include "Bob.h"
#include "apio24_magic_alice.cpp"
using namespace std;
int toggled2[500];
long long Bob(vector <pair<int,int> > adj){
long long xorhash=463222221001217544,ta,tb,ans;
for(int i=0;i<adj.size();i++){
ta=(adj[i].first-1)/34;
tb=(adj[i].second-1)/34;
if(ta==tb&&ta<=60){
toggled2[ta]=1;
}
}
ans=0;
for(int i=0;i<=60;i++){
if(toggled2[i]){
//cout<<i<<" ";
ans|= 1ll << i;
}
}
ans^=xorhash;
return ans;
}
/*
int main(){
cout<<Bob(Alice());
}*/