oj.uz

Submission #478814

# Submission time Handle Problem Language Result Execution time Memory
478814 2021-10-08T12:45:17 Z inksamurai Konstrukcija (COCI20_konstrukcija) C++17
50 / 110
 3 ms 716 KB 
#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;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 588 KB Correct.
2 Correct 1 ms 588 KB Correct.
3 Correct 1 ms 588 KB Correct.
4 Correct 1 ms 588 KB Correct.
5 Correct 1 ms 588 KB Correct.

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 588 KB Correct.
2 Correct 1 ms 588 KB Correct.
3 Correct 1 ms 588 KB Correct.
4 Correct 1 ms 588 KB Correct.
5 Correct 1 ms 588 KB Correct.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 588 KB Correct.
2 Correct 1 ms 588 KB Correct.
3 Correct 1 ms 588 KB Correct.
4 Correct 1 ms 588 KB Correct.
5 Correct 1 ms 588 KB Correct.
6 Correct 1 ms 588 KB Correct.
7 Correct 1 ms 588 KB Correct.
8 Correct 1 ms 588 KB Correct.
9 Correct 1 ms 588 KB Correct.
10 Correct 1 ms 588 KB Correct.
11 Correct 1 ms 588 KB Correct.
12 Correct 1 ms 588 KB Correct.
13 Correct 1 ms 588 KB Correct.
14 Correct 1 ms 588 KB Correct.
15 Correct 1 ms 588 KB Correct.

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 588 KB Correct.
2 Correct 1 ms 588 KB Correct.
3 Correct 1 ms 588 KB Correct.
4 Correct 1 ms 588 KB Correct.
5 Correct 1 ms 588 KB Correct.
6 Correct 1 ms 588 KB Correct.
7 Correct 1 ms 588 KB Correct.
8 Correct 1 ms 588 KB Correct.
9 Correct 1 ms 588 KB Correct.
10 Correct 1 ms 588 KB Correct.
11 Correct 1 ms 588 KB Correct.
12 Correct 1 ms 588 KB Correct.
13 Correct 1 ms 588 KB Correct.
14 Correct 1 ms 588 KB Correct.
15 Correct 1 ms 588 KB Correct.
16 Incorrect 3 ms 716 KB Integer parameter [name=N] equals to 1929, violates the range [1, 1000]
17 Halted 0 ms 0 KB -