Submission #997067

#TimeUsernameProblemLanguageResultExecution timeMemory
997067huutuanMagic Show (APIO24_show)C++17
100 / 100
6 ms25400 KiB
#include <vector> #include "Alice.h" // you may define some global variables, but it does not work if you try to transfer any information from function Alice() to function Bob() through these variables. // you had better not use the same global variables in function Alice() and in function Bob(). #include <bits/stdc++.h> using namespace std; #define int long long namespace Alice_solver{ const int BIT=64; int c[100][100]; vector<int> encode(int x){ vector<int> ans(BIT); for (int i=0, rem=BIT/2; i<BIT; ++i){ if (x>=c[BIT-i-1][rem-1]){ x-=c[BIT-i-1][rem-1]; --rem; ans[i]=1; } } return ans; } int decode(vector<int> v){ int ans=0; for (int i=0, rem=BIT/2; i<BIT; ++i){ if (v[i]){ ans+=c[BIT-i-1][rem-1]; --rem; } } return ans; } int mp[5000], rmp[5000]; mt19937_64 rng(69420); int SUS; void precalc(){ for (int i=0; i<=BIT; ++i) c[i][0]=c[i][i]=1; for (int i=1; i<=BIT; ++i){ for (int j=1; j<i; ++j) c[i][j]=c[i-1][j-1]+c[i-1][j]; } iota(mp, mp+5000, 0); shuffle(mp, mp+5000, rng); for (int i=0; i<5000; ++i) rmp[mp[i]]=i; SUS=uniform_int_distribution<int>(0, 1ll<<59)(rng); } vector<pair<int32_t, int32_t>> solve(){ precalc(); long long x=setN(5000); x^=SUS; vector<int> v=encode(x); for (int i:v) cerr << i; cerr << endl; vector<pair<int32_t, int32_t>> ans; for (int i=0; i<5000/(BIT+2)*(BIT+2); i+=BIT+2){ for (int j=0; j<BIT; ++j){ int t1=uniform_int_distribution<int>(5000/(BIT+2)*(BIT+2), 4999)(rng); int t2=t1; while (t1==t2) t2=uniform_int_distribution<int>(5000/(BIT+2)*(BIT+2), 4999)(rng); if (v[j]){ ans.emplace_back(i+j, t1); }else{ ans.emplace_back(i+j, t2); } } int t=uniform_int_distribution<int>(5000/(BIT+2)*(BIT+2), 4999)(rng); ans.emplace_back(t, i+BIT); ans.emplace_back(t, i+BIT+1); } for (int i=5000/(BIT+2)*(BIT+2)+1; i<5000; ++i) ans.emplace_back(i-1, i); for (auto &i:ans) i.first=mp[i.first]+1, i.second=mp[i.second]+1; return ans; } } vector<pair<int32_t,int32_t>> Alice(){ // add your code here // change below into your code return Alice_solver::solve(); }
#include <vector> #include "Bob.h" // you may define some global variables, but it does not work if you try to transfer any information from function Alice() to function Bob() through these variables. // you had better not use the same global variables in function Alice() and in function Bob(). #include <bits/stdc++.h> using namespace std; #define int long long namespace Bob_solver{ const int BIT=64; int c[100][100]; vector<int> encode(int x){ vector<int> ans(BIT); for (int i=0, rem=BIT/2; i<BIT; ++i){ if (x>=c[BIT-i-1][rem-1]){ x-=c[BIT-i-1][rem-1]; --rem; ans[i]=1; } } return ans; } int decode(vector<int> v){ int ans=0; for (int i=0, rem=BIT/2; i<BIT; ++i){ if (v[i]){ ans+=c[BIT-i-1][rem-1]; --rem; } } return ans; } int mp[5000], rmp[5000]; mt19937_64 rng(69420); int SUS; void precalc(){ for (int i=0; i<=BIT; ++i) c[i][0]=c[i][i]=1; for (int i=1; i<=BIT; ++i){ for (int j=1; j<i; ++j) c[i][j]=c[i-1][j-1]+c[i-1][j]; } iota(mp, mp+5000, 0); shuffle(mp, mp+5000, rng); for (int i=0; i<5000; ++i) rmp[mp[i]]=i; SUS=uniform_int_distribution<int>(0, 1ll<<59)(rng); } bool adj[5000][5000]; int solve(vector<pair<int32_t, int32_t>> edge){ precalc(); for (auto &i:edge) i.first=rmp[i.first-1], i.second=rmp[i.second-1], adj[i.first][i.second]=adj[i.second][i.first]=1; vector<int> v(BIT); for (int i=0; i<5000/(BIT+2)*(BIT+2); i+=BIT+2){ for (int j=0; j<BIT; ++j){ int t1=uniform_int_distribution<int>(5000/(BIT+2)*(BIT+2), 4999)(rng); int t2=t1; while (t1==t2) t2=uniform_int_distribution<int>(5000/(BIT+2)*(BIT+2), 4999)(rng); if (adj[i+j][t1]) v[j]=1; } int t=uniform_int_distribution<int>(5000/(BIT+2)*(BIT+2), 4999)(rng); } for (int i:v) cerr << i; cerr << endl; return decode(v)^SUS; } } long long Bob(vector<pair<int32_t,int32_t>> V){ // add your code here // return 3; // change this into your code return Bob_solver::solve(V); }

Compilation message (stderr)

Bob.cpp: In function 'long long int Bob_solver::solve(std::vector<std::pair<int, int> >)':
Bob.cpp:62:14: warning: unused variable 't' [-Wunused-variable]
   62 |          int t=uniform_int_distribution<int>(5000/(BIT+2)*(BIT+2), 4999)(rng);
      |              ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...