Submission #66812421

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;

#define INF 1234567890
#define ll long long
#define MOD 998244353

int T;
int N;
int L[505], R[505], P[505];
vector<int> g[505], v[505], res;

bool vis[505];
void DFS(int n, int st)
{
	vis[n] = true;
	if (st != n) v[st].push_back(n); // st는 n들에 의존성을 가진다.
	for(int next : g[n])
		if (!vis[next])
			DFS(next, st);
}

void Solve(int i)
{
	while(1)
	{
		int mn = INF;
		for(int j : v[i])
			if (!vis[j])
				mn = min(mn, j);
		if (mn == INF) // 의존성이 전부 해결된 경우
		{
			vis[i] = true;
			res.push_back(i);
			return;
		}
		Solve(mn);
	}
}

int main()
{
	ios::sync_with_stdio(0); cin.tie(0);
	cin.exceptions(ios::badbit | ios::failbit);
	cin >> T;
	while(T--)
	{
		cin >> N;
		for(int i=1; i<=N; i++)
			cin >> L[i] >> R[i];

		// clear
		for(int i=1; i<=N; i++)
		{
			g[i].clear();
			v[i].clear();
		}
		res.clear();

		for(int i=1; i<=N; i++)
			for(int j=1; j<=N; j++)
				if (L[i] < L[j] && R[j] < R[i])
					g[i].push_back(j); // 위상정렬 역관계, P[j] < P[i]이어야 한다.
		
		for(int i=1; i<=N; i++)
		{
			memset(vis, 0, sizeof(vis));
			DFS(i, i);
		}

		// 1번 사람, 2번 사람, ...을 차례대로 뽑아야 한다.
		memset(vis, 0, sizeof(vis));
		for(int i=1; i<=N; i++)
			if (!vis[i])
				Solve(i);
		
		// res는 seat를 뽑는 순서이다. 사람을 뽑는 순서는 inv perm임
		int k = 1;
		for(int i : res)
			P[i] = k++;
		
		for(int i=1; i<=N; i++)
			cout << P[i] << " ";
		cout << "\n";
	}
	return 0;
}

Submission Info

Judge Result