Submission #1313448

#TimeUsernameProblemLanguageResultExecution timeMemory
1313448neonglitchSubway (info1cup19_subway)C++20
100 / 100
32 ms1052 KiB
#include <iostream>
using namespace std;
const int N=1e6+100;
int par[N];
int f(int n)
{
	return (n*(n-1))/2;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int k;
	cin>>k;
	int n=0;
	while(f(n+1)<=k)
	{
		n++;
	}
	k-=f(n);
	// this will be atmost the sum of 
	for(int i=0;i<n;i++)
	{
		par[i]=i-1;
	}
	// 0 -1
	// 1 0
	int lst=n;
	for(int i=n-1;i>=0;i--)
	{
		// if we add as child of i the number of ancestor are i+1
		while(k>=(i+1))
		{
			k-=(i+1);
			par[lst]=i;
			lst++;
		}
	}
	cout<<lst<<endl;
	for(int i=0;i<lst;i++)cout<<i<<' '<<par[i]<<endl;;
	// cout<<lst<<endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...