QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#500747#6407. Classical A+B Problemucup-team2307#Compile Error//C++203.7kb2024-08-01 19:34:232024-08-01 19:34:24

Judging History

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

  • [2024-08-01 19:34:24]
  • 评测
查看
  • [2024-08-01 19:34:23]
  • 提交

answer

#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;
map<array<int, 2>, int> id;
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});
		}
		
		
		id.clear();
		for(int i = 0; i < pts.size(); i++) 
		    id[pts[i]] = i;
	}

	int getX() {
		while(Xq.size()) {
			auto [cnt, x] = Xq.top();
			if(X_to_pts[x].size() == cnt) {
				return x;
			} Xq.pop();
		}
		return -1;
	}
	int getY() {
		while(Yq.size()) {
			auto [cnt, y] = Yq.top();
			if(Y_to_pts[y].size() == cnt) {
				return y;
			} Yq.pop();
		}
		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);
		    break;
		}
		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);
	    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';
	        cout << x << " " << y << " " << u << " " << v << endl;
	    }
	}
}/*
2 piles sum <= 2
0 0
0 1
0 2
1 1
*/
源文件, 语言: C++20

詳細信息 

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:58: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]
   58 |                 Xq.push({X_to_pts[x].size(), x});
      |                          ~~~~~~~~~~~~~~~~^~
answer.code:59: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]
   59 |                 Yq.push({Y_to_pts[y].size(), y});
      |                          ~~~~~~~~~~~~~~~~^~
answer.code: At global scope:
answer.code:112:2: warning: ISO C++ forbids declaration of ‘main’ with no type [-Wreturn-type]
  112 |  main() {
      |  ^~~~
In file included from /usr/include/c++/13/string:43,
                 from /usr/include/c++/13/bitset:52,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:52,
                 from answer.code:3:
/usr/include/c++/13/bits/allocator.h: In destructor ‘constexpr std::_Rb_tree<std::array<int, 2>, std::pair<const std::array<int, 2>, int>, std::_Select1st<std::pair<const std::array<int, 2>, int> >, std::less<std::array<int, 2> >, std::allocator<std::pair<const std::array<int, 2>, int> > >::_Rb_tree_impl<std::less<std::array<int, 2> >, true>::~_Rb_tree_impl()’:
/usr/include/c++/13/bits/allocator.h:184:7: error: inlining failed in call to ‘always_inline’ ‘constexpr std::allocator< <template-parameter-1-1> >::~allocator() noexcept [with _Tp = std::_Rb_tree_node<std::pair<const std::array<int, 2>, int> >]’: target specific option mismatch
  184 |       ~allocator() _GLIBCXX_NOTHROW { }
      |       ^
In file included from /usr/include/c++/13/map:62,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:152:
/usr/include/c++/13/bits/stl_tree.h:662:16: note: called from here
  662 |         struct _Rb_tree_impl
      |                ^~~~~~~~~~~~~
English 繁體中文 简体中文

伺服器時間: 2024-12-02 23:40:30 | 開源專案