本题正解为 $O(n)$，但实测 $O(n^2)$ 做法能且跑得飞快过（提交记录）。
我认为原因是 $O(n^2)$ 做法在每次 check 一个点能否作为起点时，只要发现不合法就立即 return，这使得在随机数据下， check 的平均时间复杂度远小于 $O(n)$。
但这是容易卡掉的。只要构造一个数据使得 check 无法及时 return 即可，例如全为 1 的数据。为防止特判，可以随机修改少量点的值。（修改的值不能过多，否则 $O(n^2)$ 可以跑过）
generator:

// 6170 generator
#include<bits/stdc++.h>

using namespace std;

constexpr int n = 1e5;

int main()
{
	freopen("P6170.in", "w", stdout);
	
	cout << n << endl;
	vector<int> c(n, 1);
	
	mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
	uniform_int_distribution<> d(0, n - 1);
	for(int i = 1; i <= 5; i++) // 随机修改 
	{
		int x = d(rng), y = d(rng);
		while(!c[x]) x = d(rng);
		c[x]--, c[y]++;
//		cerr << x << ' ' << y << endl;
	}
	
	for(int x: c) cout << x << endl;
	
	return 0;
}

实测构造出来的数据可以把 $O(n^2)$ 算法卡到 10s 左右（在我的电脑上）。