Submission #1196705

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196705		shjeong	Magic Show (APIO24_show)	C++20	0 / 100	2 ms	364 KiB

Alice

#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;
}

Bob

#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 == 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);
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 30
• Subtask 3: 0 / 65