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>
//eolibraries
#define lnf 3999999999999999999
#define inf 999999999
#define fi first
#define se second
#define pb push_back
#define all(c) (c).begin(),(c).end()
#define sz(c) (ll)(c).size()
#define make_unique(a) sort(all(a)),a.erase(unique(all(a)),a.end());
#define rep(i,n) for(ll i=0;i<n;i++)
#define drep(i,n) for(ll i=n-1;i>=0;i--)
#define crep(i,x,n) for(ll i=x;i<n;i++)
#define vec(...) vector<__VA_ARGS__>
#define _3ioVv0Q ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
//eodefine
using namespace std;
typedef long long ll;
typedef long double ld;
using pii=pair<ll,ll>;
using tpii=pair<ll,pii>;
using vi=vec(ll);
const ll mxn=12000;
int main(){
_3ioVv0Q;
ll k;
cin>>k;
const ll root=0;
ll nodes=1;
vec(vi) adj(mxn);
auto push=[&](ll u,ll v){
adj[u].pb(v);
};
ll magical=mxn;
auto f=[&](ll x,ll type){
vi parent;
rep(t,type+1){
parent.pb(-1);
}
while(x>0){
rep(t,type+1){
if(parent[0]==-1){
push(root,nodes);
}else{
rep(ot,type+1){
push(parent[ot],nodes);
}
}
nodes++;
}
parent.clear();
rep(t,type+1){
parent.pb(nodes-(t+1));
}
x=x-1;
}
if(parent[0]!=-1){
rep(t,type+1){
push(parent[t],magical);
}
}else{
push(root,magical);
}
};
push(0,nodes);
nodes++;
push(0,nodes);
push(nodes,magical);
push(nodes-1,magical);
nodes++;
ll now=1;
if(k>0){
vec(tpii) candies;
crep(x,2,9){
ll nowval=1;
rep(j,60){
if(nowval>k) break;
if(j%2){
candies.pb({nowval+1,{x,j}});
}
nowval*=x;
}
}
sort(all(candies));
reverse(all(candies));
while(now<k){
rep(j,sz(candies)){
ll val=candies[j].fi;
ll type=candies[j].se.fi;
ll x=candies[j].se.se;
if(now+val<=k){
now+=val;
f(x,type);
}
}
if(now+1<=k){
push(0,nodes);
push(nodes,magical);
nodes++;
now++;
}
}
}else{
vec(tpii) candies;
crep(x,2,9){
ll nowval=1;
rep(j,60){
if(nowval>abs(k)) break;
if(j%2==0 and j>0){
candies.pb({nowval-1,{x,j}});
}
nowval*=x;
}
}
sort(all(candies));
reverse(all(candies));
while(now>k){
rep(j,sz(candies)){
ll val=candies[j].fi;
ll type=candies[j].se.fi;
ll x=candies[j].se.se;
if(now-val>=k){
now-=val;
f(x,type);
}
}
if(now-1>=k){
push(0,nodes);
push(nodes,magical);
nodes++;
push(0,nodes);
push(nodes,magical);
nodes++;
f(2,2);
now--;
}
}
}
ll m=0;
rep(v,mxn){
m+=sz(adj[v]);
}
cout<<nodes+1<<" "<<m<<"\n";
rep(i,mxn){
ll v=i;
for(auto u : adj[i]){
cout<<(v==magical?nodes:v)+1<<" "<<(u==magical?nodes:u)+1<<"\n";
}
}
//
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |