結果

問題 No.3074 Divide Points Fairly
ユーザー daiota
提出日時 2025-03-28 23:29:50
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,211 bytes
コンパイル時間 1,688 ms
コンパイル使用メモリ 171,576 KB
実行使用メモリ 22,272 KB
最終ジャッジ日時 2025-03-28 23:30:15
合計ジャッジ時間 8,789 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 27 WA * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll,ll> P;
#define REP(i,n) for(ll i=0;i<ll(n);i++)









int main(void){
	cin.tie(nullptr);  ios_base::sync_with_stdio(false);
	ll i,j;


	ll N;
	cin >> N;


	map<ll,vector<ll>> mx,my;
	vector<ll> x(2*N+1),y(2*N+1);
	for(i=1;i<=2*N;i++){
		ll X,Y;
		cin >> X >> Y;

		x[i]=X;
		y[i]=Y;
		mx[X].push_back(Y);
		my[Y].push_back(X);
	}


	ll s=0,p=-1,q=-1;
	for(auto e:mx){
		s+=(ll)mx[e.first].size();
		if(s==N){
			p=e.first;
			break;
		}
		else if(s>N) q=e.first;
	}

	if(p!=-1){
		cout << 2 << ' ' << 0 << ' ' << -2*p-1 << endl;
		return 0;
	}


	ll pp=-1,qq=-1;
	s=0;
	for(auto e:my){
		s+=(ll)my[e.first].size();
		if(s==N){
			pp=e.first;
			break;
		}
		else if(s>N) qq=e.first;
	}

	if(pp!=-1){
		cout << 0 << ' ' << 2 << ' ' << -2*pp-1 << endl;
		return 0;
	}


    ll ng=-10000000000-1,ok=10000000000+1;
    while(ok-ng>1){

         ll m=(ok+ng)/2;

         ll t=0;
         for(i=1;i<=2*N;i++){
        	 if(x[i]!=q) continue;
        	 if(y[i]>500000*q+m) t++;
         }

          if(t>=N) ok=m;
          else ng=m;

      }



     cout << 500000 << ' ' << -1 << ' ' << ok << endl;












	return 0;
}
0