Submission #429892

#	Time	Username	Problem	Language	Result	Execution time	Memory
429892		songc	Power plants (CPSPC17_power)	C++14	35 / 100	6116 ms	224044 KiB

Main

#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define lb lower_bound
#define MOD 1000000007
#define HASH 7000003
#define INF (1ll<<61)
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
typedef pair<LL,int> pli;

int N, M, Q, num;
int chk[101010];
pii B[101010];
LL ans, X[101010], Y[101010], K;
vector<int> V[101010], ansX, ansY;
vector<pli> H[7070707];

int bid(LL x, LL k){
	int lo=0, hi=MOD, ret=0;
	while (lo<=hi){
		LL m=lo+hi>>1;
		if (m*m <= x*x/k) ret=m, lo=m+1;
		else hi=m-1;
	}
	return ret;
}

inline int Hash(int x, int y){return (((LL)(x+5)*MOD + (y+5)) ^ 19059) % HASH;}

int id(int x, int y){
	int t = Hash(x, y);
	for (pli it : H[t]) if (it.fi == (LL)x*MOD+y) return it.se;
	return -1;
}

bool dfs(int u, int c){
	if (chk[u]) return chk[u]*c < 0;
	chk[u] = c;
	for (int dx=-1; dx<=1; dx++) for (int dy=-1; dy<=1; dy++){
		int t = id(B[u].fi+dx, B[u].se+dy);
		if (t < 0) continue;
		for (int v : V[t]) if (v != u && (X[u]-X[v])*(X[u]-X[v])+(Y[u]-Y[v])*(Y[u]-Y[v]) <= K){
			if (dfs(v, -c)) return true;
		}
	}
	return false;
}

bool f(){
	for (int i=0; i<num; i++) V[i].clear();
	for (int i=1; i<=N; i++) H[Hash(B[i].fi, B[i].se)].clear();
	for (int i=1; i<=N; i++) chk[i] = 0;
	num = 0;
	for (int i=1; i<=N; i++){
		B[i].fi = bid(X[i], K);
		B[i].se = bid(Y[i], K);
		if (id(B[i].fi, B[i].se) < 0){
			H[Hash(B[i].fi, B[i].se)].pb(pli((LL)MOD*B[i].fi + B[i].se, num));
			num++;
		}
	}
	for (int i=1; i<=N; i++){
		int t = id(B[i].fi, B[i].se);
		V[t].pb(i);
		if (V[t].size() > 9) return false;
	}
	for (int i=1; i<=N; i++){
		if (chk[i]) continue;
		if (dfs(i, 1)) return false;
	}
	return true;
}

int main(){
	scanf("%d", &N);
	for (int i=1; i<=N; i++) scanf("%lld %lld", &X[i], &Y[i]);
	LL lo=0, hi=INF;
	while (lo<=hi){
		LL m = lo+hi>>1;
		K = m;
		if (f()) ans = m, lo = m + 1;
		else hi = m - 1;
	}
	printf("%lld\n", ans+1);
	K = ans;
	f();
	for (int i=1; i<=N; i++){
		if (chk[i] > 0) ansX.pb(i);
		else ansY.pb(i);
	}
	printf("%d\n", ansX.size());
	for (int x : ansX) printf("%d ", x);
	printf("\n");
	printf("%d\n", ansY.size());
	for (int x : ansY) printf("%d ", x);
	printf("\n");
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int bid(LL, LL)':
Main.cpp:27:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 |   LL m=lo+hi>>1;
      |        ~~^~~
Main.cpp: In function 'int main()':
Main.cpp:85:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   85 |   LL m = lo+hi>>1;
      |          ~~^~~
Main.cpp:97:11: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wformat=]
   97 |  printf("%d\n", ansX.size());
      |          ~^     ~~~~~~~~~~~
      |           |              |
      |           int            std::vector<int>::size_type {aka long unsigned int}
      |          %ld
Main.cpp:100:11: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wformat=]
  100 |  printf("%d\n", ansY.size());
      |          ~^     ~~~~~~~~~~~
      |           |              |
      |           int            std::vector<int>::size_type {aka long unsigned int}
      |          %ld
Main.cpp:81:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
Main.cpp:82:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |  for (int i=1; i<=N; i++) scanf("%lld %lld", &X[i], &Y[i]);
      |                           ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 25 / 25
• Subtask 3: 0 / 65