제출 #687554

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
687554		NotLinux	Parking (CEOI22_parking)	C++17	10 / 100	115 ms	8260 KiB

Main

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 7;
int park[N][2],vis[N],col,sp;
pair < int , int > indx[N][2];
queue < int > top,bottom,consider,space;
signed main(){
	int n,m;cin >> n >> m;
	for(int i=0;i<m;i++){
		cin >> park[i][0] >> park[i][1];

		if(vis[park[i][0]]==0){
			indx[park[i][0]][0].first = i;
			indx[park[i][0]][0].second = 0;
			vis[park[i][0]] = 1;
		}
		else{
			indx[park[i][0]][1].first = i;
			indx[park[i][0]][1].second = 0;
		}

		if(vis[park[i][1]]==0){
			indx[park[i][1]][0].first = i;
			indx[park[i][1]][0].second = 1;
			vis[park[i][1]] = 1;
		}
		else{
			indx[park[i][1]][1].first = i;
			indx[park[i][1]][1].second = 1;
		}
	}

	int sayac = 0;
	vector < pair < int , int > > answer;
	fill(vis , vis+N , 0);

	for(int i = 0;i<m;i++){
		if(park[i][0] == park[i][1]){
			if(park[i][0]){
				sayac++;
				vis[park[i][0]] = 1;
			}
			else space.push(i);
		}
	}

	for(col = 1;col<=n;col++){
		if(indx[col][0].second == 1 and indx[col][1].second == 1)top.push(col);
		else if((park[indx[col][0].first][1] == 0 or park[indx[col][0].first][1] == col) and (park[indx[col][1].first][1] == 0 or park[indx[col][1].first][1] == col))bottom.push(col);
	}
	int bruh = 0;
	while(top.size() or bottom.size()){
		bruh++;
		if(bruh > 4*n){
			break;
		}
		while(bottom.size()){
			col = bottom.front();
			bottom.pop();

			if(vis[col])continue;
			vis[col] = 1;
			sayac++;	

			if(indx[col][0].second == 0 and indx[col][1].second == 0){
				answer.push_back({indx[col][0].first,indx[col][1].first});
				park[indx[col][1].first][1] = col;
				park[indx[col][0].first][0] = 0;
				space.push(indx[col][0].first);
			}
			else{
				if(indx[col][0].second == 1){
					answer.push_back({indx[col][0].first,indx[col][1].first});
					park[indx[col][1].first][1] = col;
					park[indx[col][0].first][1] = 0;	
					consider.push(park[indx[col][0].first][0]);
				}
				else{
					answer.push_back({indx[col][1].first,indx[col][0].first});
					park[indx[col][0].first][1] = col;	
					park[indx[col][1].first][1] = 0;
					consider.push(park[indx[col][1].first][0]);	
				}
			}
		}
		while(space.size() and top.size()){
			col = top.front();
			top.pop();

			if(vis[col])continue;
			vis[col] = 1;
			sayac++;	

			sp = space.front();
			space.pop();
			answer.push_back({indx[col][0].first,sp});
			answer.push_back({indx[col][1].first,sp});
			park[sp][0] = col;
			park[sp][1] = col;
			park[indx[col][0].first][1] = 0;
			park[indx[col][1].first][1] = 0;
			consider.push(park[indx[col][0].first][0]);
			consider.push(park[indx[col][1].first][0]);
		}
		while(consider.size()){
			col = consider.front();
			consider.pop();

			if(vis[col])continue;

			if(indx[col][0].second == 1 and indx[col][1].second == 1)top.push(col);
			else if((park[indx[col][0].first][1] == 0 or park[indx[col][0].first][1] == col) and (park[indx[col][1].first][1] == 0 or park[indx[col][1].first][1] == col))bottom.push(col);
		}
	}	

	if(sayac < n)cout << "-1" << "\n";
	else{
		cout << answer.size() << "\n";
		for(auto itr : answer)cout << itr.first+1 << " " << itr.second+1 << "\n";
	}

	cout << endl;
}

• Subtask 1: 0 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 25
• Subtask 4: 0 / 15
• Subtask 5: 0 / 25
• Subtask 6: 0 / 15