제출 #1313448

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1313448		neonglitch	Subway (info1cup19_subway)	C++20	100 / 100	32 ms	1052 KiB

subway

#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;
}

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 50 / 50