oj.uz

Submission #429717

# Submission time Handle Problem Language Result Execution time Memory
429717 2021-06-16T08:54:49 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 111 ms 168644 KB Output is correct
2 Correct 121 ms 168708 KB Output is correct
3 Correct 126 ms 168736 KB Output is correct
4 Correct 118 ms 168644 KB Output is correct
5 Correct 114 ms 168632 KB Output is correct
6 Correct 112 ms 168612 KB Output is correct
7 Correct 111 ms 168632 KB Output is correct
8 Correct 112 ms 168740 KB Output is correct
9 Correct 113 ms 168712 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 168644 KB Output is correct
2 Correct 121 ms 168708 KB Output is correct
3 Correct 126 ms 168736 KB Output is correct
4 Correct 118 ms 168644 KB Output is correct
5 Correct 114 ms 168632 KB Output is correct
6 Correct 112 ms 168612 KB Output is correct
7 Correct 111 ms 168632 KB Output is correct
8 Correct 112 ms 168740 KB Output is correct
9 Correct 113 ms 168712 KB Output is correct
10 Correct 147 ms 169700 KB Output is correct
11 Correct 142 ms 169496 KB Output is correct
12 Correct 148 ms 169360 KB Output is correct
13 Correct 151 ms 169812 KB Output is correct
14 Correct 174 ms 169752 KB Output is correct
15 Correct 128 ms 169076 KB Output is correct
16 Correct 147 ms 169464 KB Output is correct
17 Correct 150 ms 169636 KB Output is correct
18 Correct 158 ms 169652 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 168644 KB Output is correct
2 Correct 121 ms 168708 KB Output is correct
3 Correct 126 ms 168736 KB Output is correct
4 Correct 118 ms 168644 KB Output is correct
5 Correct 114 ms 168632 KB Output is correct
6 Correct 112 ms 168612 KB Output is correct
7 Correct 111 ms 168632 KB Output is correct
8 Correct 112 ms 168740 KB Output is correct
9 Correct 113 ms 168712 KB Output is correct
10 Correct 147 ms 169700 KB Output is correct
11 Correct 142 ms 169496 KB Output is correct
12 Correct 148 ms 169360 KB Output is correct
13 Correct 151 ms 169812 KB Output is correct
14 Correct 174 ms 169752 KB Output is correct
15 Correct 128 ms 169076 KB Output is correct
16 Correct 147 ms 169464 KB Output is correct
17 Correct 150 ms 169636 KB Output is correct
18 Correct 158 ms 169652 KB Output is correct
19 Execution timed out 6041 ms 227292 KB Time limit exceeded
20 Halted 0 ms 0 KB -