CSES - Putka Open 2025 – 1/5

Submission details
Task:	Järjestys
Sender:	Laakeri
Submission time:	2025-09-07 11:47:38 +0300
Language:	C++ (C++11)
Status:	READY
Result:	100

Feedback
group	verdict	score
#1	ACCEPTED	10
#2	ACCEPTED	10
#3	ACCEPTED	10
#4	ACCEPTED	40
#5	ACCEPTED	30

Test results
test	verdict	time	group
#1	ACCEPTED	0.01 s	1, 4, 5	details
#2	ACCEPTED	0.01 s	1, 4, 5	details
#3	ACCEPTED	0.01 s	1, 4, 5	details
#4	ACCEPTED	0.01 s	1, 4, 5	details
#5	ACCEPTED	0.01 s	1, 4, 5	details
#6	ACCEPTED	0.01 s	1, 2, 4, 5	details
#7	ACCEPTED	0.01 s	1, 3, 4, 5	details
#8	ACCEPTED	0.01 s	1, 4, 5	details
#9	ACCEPTED	0.03 s	2, 4, 5	details
#10	ACCEPTED	0.06 s	3, 4, 5	details
#11	ACCEPTED	0.03 s	4, 5	details
#12	ACCEPTED	0.03 s	4, 5	details
#13	ACCEPTED	0.03 s	4, 5	details
#14	ACCEPTED	0.04 s	4, 5	details
#15	ACCEPTED	0.11 s	2, 5	details
#16	ACCEPTED	0.28 s	3, 5	details
#17	ACCEPTED	0.11 s	5	details
#18	ACCEPTED	0.09 s	5	details
#19	ACCEPTED	0.12 s	5	details
#20	ACCEPTED	0.17 s	5	details
#21	ACCEPTED	0.20 s	5	details
#22	ACCEPTED	0.27 s	5	details

Code

#include <bits/stdc++.h>
#define F first
#define S second
typedef long long ll;
using namespace std;

struct EulerTour {
	int dir;
	vector<vector<pair<int, int> > > g;
	vector<int> used;
	void dfs(int x, vector<int>& ret) {
		int t=x;vector<int> c;
		while (1) {
			while (used[g[t].back().S]) g[t].pop_back();
			auto nx=g[t].back();
			g[t].pop_back();
			used[nx.S]=1;t=nx.F;
			c.push_back(t);
			if (t==x) break;
		}
		for (int a:c) {
			ret.push_back(a);
			while (g[a].size()>0&&used[g[a].back().S]) g[a].pop_back();
			if (g[a].size()>0) dfs(a, ret);
		}
	}
	EulerTour(vector<int>* og, int n, vector<int>& ret, int d=0):dir(d),g(n+1) {
		int i2=0;
		for (int i=1;i<=n;i++) {
			for (int nx:og[i]) {
				if (d==1||nx<=i) {
					if (d==0&&nx<i) g[nx].push_back({i, i2});
					g[i].push_back({nx, i2++});
				}
			}
		}
		used.resize(i2);
		for (int i=1;i<=n;i++) {
			if (g[i].size()>0) {
				ret.push_back(i);
				dfs(i, ret);
				break;
			}
		}
	}
};

struct SCC {
	vector<int> used;
	vector<vector<int> > g2;
	void dfs1(vector<int>* g, int x, vector<int>& ns) {
		if (used[x]==1) return;
		used[x]=1;
		for (int nx:g[x]) {
			g2[nx].push_back(x);
			dfs1(g, nx, ns);
		}
		ns.push_back(x);
	}
	void dfs2(int x, vector<int>& co) {
		if (used[x]==2) return;
		used[x]=2;
		co.push_back(x);
		for (int nx:g2[x]) dfs2(nx, co);
	}
	SCC(vector<int>* g, int n, vector<vector<int> >& ret) : used(n+1), g2(n+1) {
		vector<int> ns;
		for (int i=1;i<=n;i++) dfs1(g, i, ns);
		for (int i=n-1;i>=0;i--) {
			if (used[ns[i]]!=2) {
				ret.push_back(vector<int>());
				dfs2(ns[i], ret.back());
			}
		}
	}
};

int su[1010];
vector<int> g[1010];
int ind[1010];
int outd[1010];

void solve(){
	for (int i=0;i<1010;i++){
		su[i]=0;
		g[i].clear();
		g[i].shrink_to_fit();
		ind[i]=0;
		outd[i]=0;
	}
	int n;
	cin>>n;
	vector<int> cs;
	multiset<pair<int,int>> in;
	for (int i=0;i<n;i++){
		int a,b;
		cin>>a>>b;
		in.insert({a,b});
		cs.push_back(a);
		cs.push_back(b);
	}
	in.insert({1000000000+1, 0});
	cs.push_back(0);
	cs.push_back(1000000000+1);
	sort(cs.begin(), cs.end());
	cs.erase(unique(cs.begin(), cs.end()), cs.end());
	map<int,int> ccmap;
	for (int i=0;i<(int)cs.size();i++){
		ccmap[cs[i]] = i+1;
	}
	int mac = (int)cs.size();
	assert(mac<1005);
	vector<pair<int,int>> incc;
	for (auto t:in){
		assert(ccmap.count(t.F));
		assert(ccmap.count(t.S));
		incc.push_back({ccmap[t.F],ccmap[t.S]});
		assert(incc.back().F >= 1 && incc.back().F <= mac);
		assert(incc.back().S >= 1 && incc.back().S <= mac);
	}
	for (auto t:incc){
		if (t.F<t.S){
			for (int i=t.F;i<t.S;i++){
				su[i]++;
			}
		} else if (t.F>t.S){
			for (int i=t.S;i<t.F;i++){
				su[i]--;
			}
		}
	}
	for (auto t:incc){
		g[t.F].push_back(t.S);
		ind[t.S]++;
		outd[t.F]++;
	}
	for (int i=0;i<1010;i++){
		if (su[i]>0){
			cout<<"NO"<<endl;
			return;
		}
		if (su[i]<0){
			g[i].push_back(i+1);
			ind[i+1]++;
			outd[i]++;
			su[i]++;
		}
	}

	int fo=1;
	while (fo){
		fo=0;
		for (int i=1;i<1010;i++){
			if (su[i]>=0&&su[i-1]<0){
				fo=1;
				for (int j=i-1;;j--){
					if (j<0 || su[j]>=0){
						assert(j+1<i);
						g[j+1].push_back(i);
						ind[i]++;
						outd[j+1]++;
						for (int j2=j+1;j2<i;j2++){
							su[j2]++;
						}
						break;
					}
				}
			}
		}
	}
	for (int i=0;i<1010;i++){
		assert(ind[i]==outd[i]);
		assert(su[i]==0);
	}
	vector<vector<int>> sccs;
	SCC scc(g, mac, sccs);
	if (sccs.size() >= 2){
		cout<<"NO"<<endl;
		return;
	}
	vector<int> et;
	EulerTour ett(g, mac, et, 1);
	cout<<"YES"<<endl;
	int sp=-1;
	for (int i=0;i<(int)et.size();i++){
		if (et[i] == 1){
			sp=i;
		}
	}
	assert(sp>=0);
	in.erase({1000000000+1, 0});
	for (int i=0;i<(int)et.size()-1;i++){
		int ti=(i+sp)%(int)et.size();
		int nti=(i+sp+1)%(int)et.size();
		int a=cs[et[ti]-1];
		int b=cs[et[nti]-1];
		auto it=in.find({a,b});
		if (it!=in.end()){
			in.erase(it);
			cout<<a<<" "<<b<<endl;
		}
	}
	assert(in.size()==0);
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int tcs;
	cin>>tcs;
	for (int tc=0;tc<tcs;tc++){
		solve();
	}
}

Test details

Test 1

Group: 1, 4, 5

Verdict: ACCEPTED

input
`100 1 74 75 1 100 43 ...` view save

correct output
`YES 74 75 YES 100 43 YES ...` view save

user output
`YES 74 75 YES 100 43 YES ...` Truncated

Test 2

Group: 1, 4, 5

Verdict: ACCEPTED

input
`100 2 80 54 51 61 2 ...` view save

correct output
`YES 51 61 80 54 YES 2 64 ...` view save

user output
`YES 51 61 80 54 YES 2 64 ...` Truncated

Test 3

Group: 1, 4, 5

Verdict: ACCEPTED

input
`100 3 3 74 91 45 100 24 ...` view save

correct output
`YES 3 74 100 24 91 45 YES ...` view save

user output
`YES 3 74 91 45 100 24 YES ...` Truncated

Test 4

Group: 1, 4, 5

Verdict: ACCEPTED

input
`100 4 88 50 62 41 12 86 ...` view save

correct output
`YES 12 86 88 50 62 41 66 93 ...` view save

user output
`YES 12 86 88 50 62 41 66 93 ...` Truncated

Test 5

Group: 1, 4, 5

Verdict: ACCEPTED

input
`100 5 82 80 80 92 5 22 ...` view save

correct output
`YES 5 22 94 13 82 80 80 92 ...` view save

user output
`YES 5 22 82 80 80 92 93 91 ...` Truncated

Test 6

Group: 1, 2, 4, 5

Verdict: ACCEPTED

input
`100 5 34 38 26 30 1 6 ...` view save

correct output
`YES 1 6 12 22 26 30 34 38 ...` view save

user output
`YES 1 6 12 22 26 30 34 38 ...` Truncated

Test 7

Group: 1, 3, 4, 5

Verdict: ACCEPTED

input
`100 5 50 40 28 25 51 7 ...` view save

correct output
`YES 51 7 50 40 47 1 17 11 ...` view save

user output
`YES 51 7 17 11 28 25 50 40 ...` Truncated

Test 8

Group: 1, 4, 5

Verdict: ACCEPTED

input
`100 5 2 2 2 1 1 1 ...` view save

correct output
`YES 1 2 2 1 2 1 1 1 ...` view save

user output
`YES 1 2 2 1 1 1 2 2 ...` Truncated

Test 9

Group: 2, 4, 5

Verdict: ACCEPTED

input
`100 100 175870020 296379324 248160539 883842002 21934885 781732852 ...` view save

correct output
`NO YES 4976156 6890135 10553287 11923223 14617057 17728163 ...` view save

user output
`NO YES 4976156 6890135 10553287 11923223 14617057 17728163 ...` Truncated

Test 10

Group: 3, 4, 5

Verdict: ACCEPTED

input
`100 100 447597377 314433951 700232436 691277009 937268439 708165426 ...` view save

correct output
`YES 998963839 391778929 995772196 257222033 995754704 553123757 994629465 247775824 ...` view save

user output
`YES 998963839 391778929 400940916 299338123 302529290 230967335 231166897 72684060 ...` Truncated

Test 11

Group: 4, 5

Verdict: ACCEPTED

input
`100 100 1 1 1 2 2 1 ...` view save

correct output
`YES 1 2 2 1 1 2 2 2 ...` view save

user output
`YES 1 2 2 1 1 2 2 1 ...` Truncated

Test 12

Group: 4, 5

Verdict: ACCEPTED

input
`100 100 7 1 6 3 10 9 ...` view save

correct output
`YES 6 7 7 8 9 10 10 10 ...` view save

user output
`YES 10 6 6 6 6 3 3 10 ...` Truncated

Test 13

Group: 4, 5

Verdict: ACCEPTED

input
`100 100 51 5 85 77 91 84 ...` view save

correct output
`YES 100 24 100 25 100 3 100 6 ...` view save

user output
`YES 100 6 96 44 44 25 86 47 ...` Truncated

Test 14

Group: 4, 5

Verdict: ACCEPTED

input
`100 100 823828194 863717310 593641073 340054211 420481158 965069109 ...` view save

correct output
`YES 999289319 634855378 996775156 433726648 983657502 55234695 981890636 112877413 ...` view save

user output
`YES 999289319 634855378 787530516 244809812 249571565 551662152 592909481 560589803 ...` Truncated

Test 15

Group: 2, 5

Verdict: ACCEPTED

input
`100 500 88724450 89315226 266915464 267648621 189301651 189661541 ...` view save

correct output
`YES 764920 1459946 1936195 2832987 3691481 4085931 4991808 5840928 ...` view save

user output
`YES 764920 1459946 1936195 2832987 3691481 4085931 4991808 5840928 ...` Truncated

Test 16

Group: 3, 5

Verdict: ACCEPTED

input
`100 500 763682761 317584504 756010800 260162861 435911339 78070399 ...` view save

correct output
`YES 998768285 3307355 998714926 628486754 997115613 820932481 993320616 554600893 ...` view save

user output
`YES 998768285 3307355 998714926 628486754 684187193 279087749 735201773 202353669 ...` Truncated

Test 17

Group: 5

Verdict: ACCEPTED

input
`100 500 2 2 2 1 1 2 ...` view save

correct output
`YES 1 2 2 2 2 1 1 2 ...` view save

user output
`YES 1 2 2 1 1 2 2 1 ...` Truncated

Test 18

Group: 5

Verdict: ACCEPTED

input
`100 500 10 6 10 10 9 10 ...` view save

correct output
`YES 2 3 3 4 4 5 5 6 ...` view save

user output
`YES 1 10 10 6 6 7 7 3 ...` Truncated

Test 19

Group: 5

Verdict: ACCEPTED

input
`100 500 85 87 89 70 70 92 ...` view save

correct output
`YES 96 97 100 67 100 10 100 97 ...` view save

user output
`YES 100 42 42 23 90 4 100 5 ...` Truncated

Test 20

Group: 5

Verdict: ACCEPTED

input
`100 500 861154169 119512584 569086662 606567153 288230434 322196278 ...` view save

correct output
`YES 999945324 969534372 999738857 240617694 999244114 722161553 999207839 557351400 ...` view save

user output
`YES 999945324 969534372 970563099 901519892 902769828 406637704 416346837 467377463 ...` Truncated

Test 21

Group: 5

Verdict: ACCEPTED

input
`100 500 116439250 401518028 280329609 193466222 674040956 209050570 ...` view save

correct output
`NO YES 773701149 773852119 987509190 315670966 977413249 510418200 ...` view save

user output
`NO YES 973938868 274722180 275014695 4271727 949227105 590300182 ...` Truncated

Test 22

Group: 5

Verdict: ACCEPTED

input
`100 500 934181189 942499518 684836806 395802802 957884803 570946201 ...` view save

correct output
`YES 999772640 505132174 999111650 140844643 999028633 888134186 999020109 291046771 ...` view save

user output
`YES 999772640 505132174 509093069 668913490 674012665 350561914 701726311 465950306 ...` Truncated

Putka Open 2025 – 1/5

Järjestys

Code

Test details

Test 1

Test 2

Test 3

Test 4

Test 5

Test 6

Test 7

Test 8

Test 9

Test 10

Test 11

Test 12

Test 13

Test 14

Test 15

Test 16

Test 17

Test 18

Test 19

Test 20

Test 21

Test 22

Tasks

Submissions (Laakeri)