Submission #478814

#TimeUsernameProblemLanguageResultExecution timeMemory
478814inksamuraiKonstrukcija (COCI20_konstrukcija)C++17
50 / 110
3 ms716 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...