QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#500733#6407. Classical A+B Problemucup-team2307#Compile Error//C++203.6kb2024-08-01 19:18:592024-08-01 19:19:00

Judging History

你现在查看的是最新测评结果

  • [2024-08-01 19:19:00]
  • 评测
  • [2024-08-01 19:18:59]
  • 提交

answer

```cpp
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2")
#include<bits/stdc++.h>
#define all(x) begin(x), end(x)
using namespace std;
using ll = long long;
struct Points {
	int n;
	vector<set<array<int, 2>>> X_to_pts, Y_to_pts;
	priority_queue<array<int, 2>> Xq, Yq;
	Points(vector<array<int, 2>> pts) : n(pts.size()), X_to_pts(n), Y_to_pts(n) {
		vector<int> X, Y;
		for(auto &[x, y] : pts) {
			X.push_back(x);
			Y.push_back(y);
		}
		sort(all(X)); sort(all(Y));
		for(auto &[x, y] : pts) {
			x = lower_bound(all(X), x) - X.begin();
			y = lower_bound(all(Y), y) - Y.begin();
			X_to_pts[x].insert({x, y});
			Y_to_pts[y].insert({x, y});
		}
		for(int i = 0; i < n; i++) {
			Xq.push({X_to_pts[i].size(), i});
			Yq.push({Y_to_pts[i].size(), i});
		}
	}

	int getX() {
		while(Xq.size()) {
			auto [cnt, x] = Xq.top(); Xq.pop();
			if(X_to_pts[x].size() == cnt) {
				return x;
			}
		}
		return -1;
	}
	int getY() {
		while(Yq.size()) {
			auto [cnt, y] = Yq.top(); Yq.pop();
			if(Y_to_pts[y].size() == cnt) {
				return y;
			}
		}
		return -1;
	}

	void delete_point(int x, int y) {
		X_to_pts[x].erase({x, y});
		Y_to_pts[y].erase({x, y});
		Xq.push({X_to_pts[x].size(), x});
		Yq.push({Y_to_pts[y].size(), y});
	}
};
vector<array<int, 4>> solve(int n, vector<array<int, 2>> pts) {
	Points p(pts);
	vector<array<int, 4>> ans;
	auto finish = [&](auto chuj) {
	    int s = chuj.size();
	    for(int i = 0; i < s - i; i++) {
	        ans.push_back({chuj[i][0], chuj[i][1], chuj[s - i][0], chuj[s - i][1]});
	    }
	};
	for(int iters = 0; iters < n; iters++) {
		int x = p.getX();
		int y = p.getY();
	    vector<array<int, 2>> chuj;
		if(p.X_to_pts[x].size() == 2*(n-iters)) {//everything has this x
		    vector<array<int, 2>> chuj;
		    chuj.insert(chuj.end(), all(p.X_to_pts[x]));
		} else if(p.Y_to_pts[y].size() == 2*(n-iters)) {//everything has this y
		    chuj.insert(chuj.end(), all(p.Y_to_pts[y]));
		} else if(p.X_to_pts[x].size() == 1) {//all x distinct
		    while(chuj.size() < 2*(n - iters)) {
		        int y = p.getY();
		        vector<array<int, 2>> tmp(all(p.Y_to_pts[y]));
		        chuj.insert(chuj.end(), all(tmp));
		        for(auto [u, v] : tmp) p.delete_point(u, v);
		    }		    
		} else if(p.Y_to_pts[y].size() == 1) {//all x distinct
		    while(chuj.size() < 2*(n - iters)) {
		        int x = p.getX();
		        vector<array<int, 2>> tmp(all(p.X_to_pts[x]));
		        chuj.insert(chuj.end(), all(tmp));
		        for(auto [u, v] : tmp) p.delete_point(u, v);
		    }		    
		}
		if(chuj.size()) {
		    finish(chuj);
		    return ans;
		}
		auto A = *p.X_to_pts[x].begin();
		if(A == array<int, 2>{x, y}) A = *p.X_to_pts[x].rbegin();
		
		
		auto B = *p.Y_to_pts[y].begin();
		if(B == array<int, 2>{x, y}) B = *p.Y_to_pts[y].rbegin();
		
		ans.push_back({A[0], A[1], B[0], B[1]});
	    p.delete_point(A[0], A[1]);
	    p.delete_point(B[0], B[1]);
	}
	return ans;
}
 main() {
	cin.tie(0)->sync_with_stdio(0);
	int T;
	cin >> T;
	while(T--) {
	    int n;
	    cin >> n;
	    vector<array<int, 2>> pts(2*n);
	    map<array<int, 2>, int> id;
	    int I = 0;
	    for(auto &[x, y] : pts) {
	        cin >> x >> y;
	        id[{x, y}] = I++;
	    }
	    auto ans = solve(n, pts);
	    int bad = 0;
	    for(auto [x, y, u, v] : ans) {
	        bad += x==u || y==v;
	    }
	    cout<< bad << '\n';
	    for(auto [x, y, u, v] : ans) {
	        cout << id[{x, y}] << " " << id[{u, v}] << '\n';
	    }
	}
}/*
2 piles sum <= 2
0 0
0 1
0 2
1 1
*/
```

Details

answer.code:1:1: error: stray ‘`’ in program
    1 | ```cpp
      | ^
answer.code:1:2: error: stray ‘`’ in program
    1 | ```cpp
      |  ^
answer.code:1:3: error: stray ‘`’ in program
    1 | ```cpp
      |   ^
answer.code:138:1: error: stray ‘`’ in program
  138 | ```
      | ^
answer.code:138:2: error: stray ‘`’ in program
  138 | ```
      |  ^
answer.code:138:3: error: stray ‘`’ in program
  138 | ```
      |   ^
answer.code:1:4: error: ‘cpp’ does not name a type
    1 | ```cpp
      |    ^~~
answer.code: In constructor ‘Points::Points(std::vector<std::array<int, 2>, std::allocator<std::array<int, 2> > >)’:
answer.code:26:50: warning: narrowing conversion of ‘(&((Points*)this)->Points::X_to_pts.std::vector<std::set<std::array<int, 2> > >::operator[](((std::vector<std::set<std::array<int, 2> > >::size_type)i)))->std::set<std::array<int, 2> >::size()’ from ‘std::set<std::array<int, 2> >::size_type’ {aka ‘long unsigned int’} to ‘int’ [-Wnarrowing]
   26 |                         Xq.push({X_to_pts[i].size(), i});
      |                                  ~~~~~~~~~~~~~~~~^~
answer.code:27:50: warning: narrowing conversion of ‘(&((Points*)this)->Points::Y_to_pts.std::vector<std::set<std::array<int, 2> > >::operator[](((std::vector<std::set<std::array<int, 2> > >::size_type)i)))->std::set<std::array<int, 2> >::size()’ from ‘std::set<std::array<int, 2> >::size_type’ {aka ‘long unsigned int’} to ‘int’ [-Wnarrowing]
   27 |                         Yq.push({Y_to_pts[i].size(), i});
      |                                  ~~~~~~~~~~~~~~~~^~
answer.code: In member function ‘void Points::delete_point(int, int)’:
answer.code:53:42: warning: narrowing conversion of ‘(&((Points*)this)->Points::X_to_pts.std::vector<std::set<std::array<int, 2> > >::operator[](((std::vector<std::set<std::array<int, 2> > >::size_type)x)))->std::set<std::array<int, 2> >::size()’ from ‘std::set<std::array<int, 2> >::size_type’ {aka ‘long unsigned int’} to ‘int’ [-Wnarrowing]
   53 |                 Xq.push({X_to_pts[x].size(), x});
      |                          ~~~~~~~~~~~~~~~~^~
answer.code:54:42: warning: narrowing conversion of ‘(&((Points*)this)->Points::Y_to_pts.std::vector<std::set<std::array<int, 2> > >::operator[](((std::vector<std::set<std::array<int, 2> > >::size_type)y)))->std::set<std::array<int, 2> >::size()’ from ‘std::set<std::array<int, 2> >::size_type’ {aka ‘long unsigned int’} to ‘int’ [-Wnarrowing]
   54 |                 Yq.push({Y_to_pts[y].size(), y});
      |                          ~~~~~~~~~~~~~~~~^~
answer.code: At global scope:
answer.code:107:2: warning: ISO C++ forbids declaration of ‘main’ with no type [-Wreturn-type]
  107 |  main() {
      |  ^~~~