oj.uz

Submission #429684

# Submission time Handle Problem Language Result Execution time Memory
429684 2021-06-16T08:41:54 Z 송준혁(#7525) Power plants (CPSPC17_power) C++17
35 / 100
 6000 ms 227292 KB 
#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];
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 <= 2*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, LL k){
	if (chk[u]) return chk[u]*c < 0;
	chk[u] = c;
	for (register int dx=-2; dx<=2; dx++) for (register int dy=-2; dy<=2; dy++){
		if (dx*dy == 4 || dx*dy == -4) continue;
		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, k)) return true;
		}
	}
	return false;
}

bool f(LL k){
	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() > 2) return false;
	}
	for (int i=1; i<=N; i++){
		if (chk[i]) continue;
		if (dfs(i, 1, k)) 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;
		if (f(m)) ans = m, lo = m + 1;
		else hi = m - 1;
	}
	printf("%lld\n", ans+1);
	f(ans);
	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

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 'bool dfs(int, int, LL)':
Main.cpp:45:20: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   45 |  for (register int dx=-2; dx<=2; dx++) for (register int dy=-2; dy<=2; dy++){
      |                    ^~
Main.cpp:45:58: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   45 |  for (register int dx=-2; dx<=2; dx++) for (register int dy=-2; dy<=2; dy++){
      |                                                          ^~
Main.cpp: In function 'int main()':
Main.cpp:86:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   86 |   LL m = lo+hi>>1;
      |          ~~^~~
Main.cpp:96:11: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wformat=]
   96 |  printf("%d\n", ansX.size());
      |          ~^     ~~~~~~~~~~~
      |           |              |
      |           int            std::vector<int>::size_type {aka long unsigned int}
      |          %ld
Main.cpp:99:11: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wformat=]
   99 |  printf("%d\n", ansY.size());
      |          ~^     ~~~~~~~~~~~
      |           |              |
      |           int            std::vector<int>::size_type {aka long unsigned int}
      |          %ld
Main.cpp:82:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
Main.cpp:83:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |  for (int i=1; i<=N; i++) scanf("%lld %lld", &X[i], &Y[i]);
      |                           ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 168752 KB Output is correct
2 Correct 118 ms 168640 KB Output is correct
3 Correct 124 ms 168632 KB Output is correct
4 Correct 109 ms 168676 KB Output is correct
5 Correct 115 ms 168656 KB Output is correct
6 Correct 107 ms 168716 KB Output is correct
7 Correct 110 ms 168864 KB Output is correct
8 Correct 111 ms 168684 KB Output is correct
9 Correct 111 ms 168732 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 168752 KB Output is correct
2 Correct 118 ms 168640 KB Output is correct
3 Correct 124 ms 168632 KB Output is correct
4 Correct 109 ms 168676 KB Output is correct
5 Correct 115 ms 168656 KB Output is correct
6 Correct 107 ms 168716 KB Output is correct
7 Correct 110 ms 168864 KB Output is correct
8 Correct 111 ms 168684 KB Output is correct
9 Correct 111 ms 168732 KB Output is correct
10 Correct 148 ms 169784 KB Output is correct
11 Correct 161 ms 169556 KB Output is correct
12 Correct 153 ms 169400 KB Output is correct
13 Correct 144 ms 169728 KB Output is correct
14 Correct 145 ms 169828 KB Output is correct
15 Correct 126 ms 169116 KB Output is correct
16 Correct 148 ms 169444 KB Output is correct
17 Correct 144 ms 169544 KB Output is correct
18 Correct 147 ms 169668 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 168752 KB Output is correct
2 Correct 118 ms 168640 KB Output is correct
3 Correct 124 ms 168632 KB Output is correct
4 Correct 109 ms 168676 KB Output is correct
5 Correct 115 ms 168656 KB Output is correct
6 Correct 107 ms 168716 KB Output is correct
7 Correct 110 ms 168864 KB Output is correct
8 Correct 111 ms 168684 KB Output is correct
9 Correct 111 ms 168732 KB Output is correct
10 Correct 148 ms 169784 KB Output is correct
11 Correct 161 ms 169556 KB Output is correct
12 Correct 153 ms 169400 KB Output is correct
13 Correct 144 ms 169728 KB Output is correct
14 Correct 145 ms 169828 KB Output is correct
15 Correct 126 ms 169116 KB Output is correct
16 Correct 148 ms 169444 KB Output is correct
17 Correct 144 ms 169544 KB Output is correct
18 Correct 147 ms 169668 KB Output is correct
19 Execution timed out 6041 ms 227292 KB Time limit exceeded
20 Halted 0 ms 0 KB -