oj.uz

Submission #687554

# Submission time Handle Problem Language Result Execution time Memory
687554 2023-01-26T14:46:41 Z NotLinux Parking (CEOI22_parking) C++17
10 / 100
 115 ms 8260 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1088 KB Output is correct
2 Correct 1 ms 1076 KB Output is correct
3 Correct 1 ms 1084 KB Output is correct
4 Incorrect 1 ms 1108 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 7380 KB Output is correct
2 Correct 115 ms 8260 KB Output is correct
3 Correct 80 ms 6596 KB Output is correct
4 Correct 77 ms 6364 KB Output is correct
5 Correct 104 ms 8228 KB Output is correct

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1108 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1108 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1108 KB Output is correct
2 Correct 2 ms 1088 KB Output is correct
3 Correct 1 ms 1108 KB Output is correct
4 Incorrect 1 ms 1108 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1088 KB Output is correct
2 Correct 1 ms 1076 KB Output is correct
3 Correct 1 ms 1084 KB Output is correct
4 Incorrect 1 ms 1108 KB Output isn't correct
5 Halted 0 ms 0 KB -