QOJ.ac

QOJ

ID提交记录ID题目HackerOwner结果提交时间测评时间
#1029#663913#21692. 【NOIP Round #3】移除石子max666dong123wth2026Failed.2024-10-21 18:37:582024-10-21 18:37:59

詳細信息

Extra Test:

Accepted
time: 677ms
memory: 3816kb

input:

60
3000
53 19
14 2
59 16
22 12
22 40
41 22
21 60
13 53
6 60
29 11
59 18
38 53
34 37
62 41
33 44
18 27
44 5
5 2
35 65
21 59
6 64
56 48
51 45
50 9
44 42
15 8
24 38
33 14
62 39
45 64
23 9
57 18
10 29
30 17
4 12
49 7
21 27
15 32
31 36
62 51
46 9
23 3
16 15
11 43
63 50
53 62
63 44
13 29
52 61
11 39
50 55...

output:

Yes
-1 2 1 4
-1 5 1 7
0 8 1 9
0 10 1 11
0 12 1 13
-3 14 1 18
0 20 1 21
0 23 1 24
0 25 1 26
-2 27 1 30
0 31 1 32
-1 34 1 36
0 37 1 38
0 39 1 40
0 43 1 44
0 45 1 46
0 47 1 48
0 49 1 50
0 51 1 52
-1 54 1 56
0 57 1 58
-2 59 1 62
0 63 1 64
1 2 2 3
1 4 2 5
1 6 2 7
1 8 2 9
1 10 2 11
1 13 2 14
1 15 2 16
0 1...

result:

ok OK (60 test cases)

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#663913#21692. 【NOIP Round #3】移除石子wth2026100 ✓365ms3764kbC++142.9kb2024-10-21 18:21:432024-10-21 18:21:44

answer

#include <cmath>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>

#define endl '\n'
#define int long long
#define inf 0x3f3f3f3f
#define lnf 0x3f3f3f3f3f3f3f3f

const bool Debug = false;

#define Debug ture

using namespace std;

void outputl (pair <int, int> x, pair <int, int> y) {
	int X = max (x.first, y.first);
	int Y = max (x.second, y.second);
	int Z = max (abs (x.first - y.first), abs (x.second - y.second));
	cout << X - Z << ".5 " << Y - Z << ' ' << X << ".5 " << Y << endl;
}

void outputr (pair <int, int> x, pair <int, int> y) {
	int X = max (x.first, y.first);
	int Y = max (x.second, y.second);
	int Z = max (abs (x.first - y.first), abs (x.second - y.second));
	cout << X - Z << ' ' << Y - Z << ' ' << X << ' ' << Y << endl;
}

const int N = 3000 + 5;

int n;
pair <int, int> _Nd[N];
vector <int> _Nw;

void Main () {
	cout << "Yes" << endl;
	
	cin >> n;
	_Nw.clear ();
	
	for (register int i = 1; i <= n; ++ i) {
		cin >> _Nd[i].first >> _Nd[i].second;
		_Nw.push_back (i);
	}
	
	sort (_Nd + 1, _Nd + n + 1);
	
	while (_Nw.size ()) {
//		for (auto it : _Nw) {
//			cout << it << ' ';
//		}
//		
//		cout << endl;
//		
		if (_Nd[_Nw[0]].first == _Nd[_Nw[1]].first || _Nd[_Nw[0]].second < _Nd[_Nw[1]].second || _Nw.size () == 2) {
			outputr (_Nd[_Nw[0]], _Nd[_Nw[1]]);
			_Nw.erase (_Nw.begin ());
			_Nw.erase (_Nw.begin ());
//			cout << "HHH" << endl;
//			cout << 
		} else {
			auto Z = _Nw.begin ();
			++ Z;
			auto Y = Z;
			++ Z;
			auto X = _Nw.begin ();
			
//			cout << * X << ' ' << _Nd[* X].first << ' ' << _Nd[* X].second << endl;
//			cout << * Y << ' ' << _Nd[* Y].first << ' ' << _Nd[* Y].second << endl;
//			cout << * Z << ' ' << _Nd[* Z].first << ' ' << _Nd[* Z].second << endl;
//			
			if (_Nd[* Z].first == _Nd[* Y].first && _Nd[* Z].second < _Nd[* X].second) {
				outputr (_Nd[* Y], _Nd[* Z]);
//				cout << * Y << ' ' << * Z << endl;
				_Nw.erase (Z);
				_Nw.erase (Y);
//				cout << "HHHHH" << endl;
//				exit (0);
			} else if (_Nd[* Z].first == _Nd[* Y].first && _Nd[* Z].second == _Nd[* X].second) {
//				exit (- 1);
				
				if (_Nd[* Z].second - _Nd[* Y].second > _Nd[* Z].first - _Nd[* X].first) {
					outputr (_Nd[* X], _Nd[* Z]);
					_Nw.erase (Z);
					_Nw.erase (X);
				} else if (_Nd[* Z].second - _Nd[* Y].second < _Nd[* Z].first - _Nd[* X].first) {
					outputr (_Nd[* Y], _Nd[* Z]);
					_Nw.erase (Z);
					_Nw.erase (Y);
				} else {
					outputl (_Nd[* Y], _Nd[* Z]);
					_Nw.erase (Z);
					_Nw.erase (Y);
				}
			} else {
				outputr (_Nd[* Y], _Nd[* X]);
				_Nw.erase (Y);
				_Nw.erase (X);
			}
		}
	}
}

signed main () {
//	ios :: sync_with_stdio (false);
//	cin.tie (0);
//	cout.tie (0);
	int T;
	cin >> T;
	
	while (T --) {
		Main ();
	}
}
/*
1
10
2 1
1 3
3 3
2 5
3 5
4 3
1 5
5 2
5 1
3 1
*/