Submission #464253

#	Time	Username	Problem	Language	Result	Execution time	Memory
464253		Jasiekstrz	Konstrukcija (COCI20_konstrukcija)	C++17	110 / 110	1 ms	332 KiB

Main

#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 / 15
• Subtask 2: 15 / 15
• Subtask 3: 20 / 20
• Subtask 4: 60 / 60