Submission #1196707

#TimeUsernameProblemLanguageResultExecution timeMemory
1196707shjeongMagic Show (APIO24_show)C++20
0 / 100
2 ms364 KiB
#include <vector> #include "Alice.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef __int128_t lll; // 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(). static bool prime[5050]; std::vector<std::pair<int,int>> Alice(){ ll x = setN(5000); for(ll i = 2 ; i <= 5000 ; i++)if(!prime[i]){ for(ll j = i*i ; j <= 5000 ; j+=i)prime[j]=1; } vector<pair<int,int>> ret; ret.push_back({1,5000}); for(int i = 2, j = 0 ; i < 5000 ; i++){ if(!prime[i])j=i; int r = x%j; if(!r)r=5000; ret.push_back({i,r}); } return ret; }
#include <vector> #include "Bob.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef __int128_t lll; #define all(x) x.begin(),x.end() #define sz(x) x.size() const ll Lnf = 1e18; // 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(). struct asdf{ lll a=0, p=0, q=0, r=0; }; static bool prime[5050]; ll solve(vector<asdf> &v){ lll P = 1; // for(auto [a,p,q,r] : v)P*=p, cout<<"(a,p) : "<<(ll)a<<", "<<(ll)p<<endl; for(auto &[a,p,q,r] : v){ q = P/p; for(ll i = 1 ; i < p ; i++)if(i*(q%p)%p == 1){r=i; break; } // assert(r!=0); } lll ret = 0; for(auto [a,p,q,r] : v){ ret += (lll)a*r*q; } ret %= P; return (ll)ret; } long long Bob(std::vector<std::pair<int,int>> V){ for(ll i = 2 ; i <= 5000 ; i++)if(!prime[i]){ for(ll j = i*i ; j <= 5000 ; j+=i)prime[j]=1; } for(auto &[a,b] : V)if(b==5000 and a!=1)b=0, swap(a,b); sort(all(V), [&](pair<int,int> a, pair<int,int> b){ if(a.second == b.second)return a.first < b.first; return a.second < b.second; }); lll P = 1; vector<asdf> v; for(ll i = 2, j = 0, k = 0 ; i < 5000 and P < Lnf ; i++){ if(!prime[i])j=i; while(k < sz(V) and V[k].second == i){ if(sz(v) and v.back().p == j); else{ P *= j; v.push_back({V[k].first,j,0,0}); } k++; if(P>=Lnf)break; } } return solve(v); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...