oj.uz

Submission #464253

# Submission time Handle Problem Language Result Execution time Memory
464253 2021-08-12T15:36:06 Z Jasiekstrz Konstrukcija (COCI20_konstrukcija) C++17
110 / 110
 1 ms 332 KB 
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N=1e3;
const int L=60;
//const int N=20;
//const int L=2;
int it;
vector<pair<int,int>> e;
vector<int> ver[2];
map<int,int> g;
map<int,int> g2;
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	long long k;
	cin>>k;
	int sgn=(k<0 ? 0:1);
	k=abs(k);

	e.emplace_back(1,2);
	e.emplace_back(1,3);
	e.emplace_back(2,4);
	e.emplace_back(3,4);
	g[0]=4;
	g2[0]=5;
	it=6;
	ver[0]={2,3};
	
	for(int i=1;i<=L;i++)
	{
		ver[1]={it,it+1,it+2};
		it+=3;

		for(auto v0:ver[0])
		{
			for(auto v1:ver[1])
				e.emplace_back(v0,v1);
		}

		for(auto v:ver[1])
		{
			e.emplace_back(v,it);
			e.emplace_back(v,it+1);
		}
		g[i]=it;
		g2[i]=it+1;
		it+=2;

		ver[0]=ver[1];
		ver[1].clear();
	}

	e.emplace_back(g[L],N);
	for(int p=L-1;p>=0;p--)
	{
		long long pot=(1LL<<p);
		if(pot<=k)
		{
			k-=pot;
			if(sgn==p%2)
				e.emplace_back(g[p],N);
			else
			{
				e.emplace_back(g[p],N);
				e.emplace_back(g2[p+1],N);
			}
		}
	}

	cout<<N<<" "<<e.size()<<"\n";
	for(auto [a,b]:e)
		cout<<a<<" "<<b<<"\n";
	return 0;
}

Subtask #1
15.0 / 15.0

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

Subtask #2
15.0 / 15.0

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

Subtask #3
20.0 / 20.0

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

Subtask #4
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Correct.
2 Correct 1 ms 308 KB Correct.
3 Correct 1 ms 332 KB Correct.
4 Correct 1 ms 332 KB Correct.
5 Correct 1 ms 332 KB Correct.
6 Correct 1 ms 332 KB Correct.
7 Correct 1 ms 332 KB Correct.
8 Correct 1 ms 332 KB Correct.
9 Correct 1 ms 332 KB Correct.
10 Correct 1 ms 332 KB Correct.
11 Correct 1 ms 332 KB Correct.
12 Correct 1 ms 332 KB Correct.
13 Correct 1 ms 332 KB Correct.
14 Correct 1 ms 332 KB Correct.
15 Correct 1 ms 332 KB Correct.
16 Correct 1 ms 332 KB Correct.
17 Correct 1 ms 332 KB Correct.
18 Correct 1 ms 332 KB Correct.
19 Correct 1 ms 332 KB Correct.
20 Correct 1 ms 332 KB Correct.
21 Correct 1 ms 312 KB Correct.
22 Correct 1 ms 332 KB Correct.
23 Correct 1 ms 332 KB Correct.
24 Correct 1 ms 332 KB Correct.
25 Correct 1 ms 332 KB Correct.
26 Correct 1 ms 312 KB Correct.
27 Correct 1 ms 332 KB Correct.