oj.uz

Submission #429725

# Submission time Handle Problem Language Result Execution time Memory
429725 2021-06-16T08:57:09 Z 송준혁(#7525) Power plants (CPSPC17_power) C++17
35 / 100
 6000 ms 227284 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], 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 <= 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){
	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)) 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() > 2) 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

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)':
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:98:11: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wformat=]
   98 |  printf("%d\n", ansX.size());
      |          ~^     ~~~~~~~~~~~
      |           |              |
      |           int            std::vector<int>::size_type {aka long unsigned int}
      |          %ld
Main.cpp:101:11: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wformat=]
  101 |  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 112 ms 168692 KB Output is correct
2 Correct 117 ms 168732 KB Output is correct
3 Correct 107 ms 168640 KB Output is correct
4 Correct 106 ms 168716 KB Output is correct
5 Correct 102 ms 168644 KB Output is correct
6 Correct 103 ms 168700 KB Output is correct
7 Correct 103 ms 168644 KB Output is correct
8 Correct 106 ms 168644 KB Output is correct
9 Correct 133 ms 168684 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 168692 KB Output is correct
2 Correct 117 ms 168732 KB Output is correct
3 Correct 107 ms 168640 KB Output is correct
4 Correct 106 ms 168716 KB Output is correct
5 Correct 102 ms 168644 KB Output is correct
6 Correct 103 ms 168700 KB Output is correct
7 Correct 103 ms 168644 KB Output is correct
8 Correct 106 ms 168644 KB Output is correct
9 Correct 133 ms 168684 KB Output is correct
10 Correct 156 ms 169776 KB Output is correct
11 Correct 137 ms 169580 KB Output is correct
12 Correct 161 ms 169412 KB Output is correct
13 Correct 138 ms 169776 KB Output is correct
14 Correct 142 ms 169744 KB Output is correct
15 Correct 124 ms 169028 KB Output is correct
16 Correct 171 ms 169332 KB Output is correct
17 Correct 180 ms 169600 KB Output is correct
18 Correct 144 ms 169668 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 168692 KB Output is correct
2 Correct 117 ms 168732 KB Output is correct
3 Correct 107 ms 168640 KB Output is correct
4 Correct 106 ms 168716 KB Output is correct
5 Correct 102 ms 168644 KB Output is correct
6 Correct 103 ms 168700 KB Output is correct
7 Correct 103 ms 168644 KB Output is correct
8 Correct 106 ms 168644 KB Output is correct
9 Correct 133 ms 168684 KB Output is correct
10 Correct 156 ms 169776 KB Output is correct
11 Correct 137 ms 169580 KB Output is correct
12 Correct 161 ms 169412 KB Output is correct
13 Correct 138 ms 169776 KB Output is correct
14 Correct 142 ms 169744 KB Output is correct
15 Correct 124 ms 169028 KB Output is correct
16 Correct 171 ms 169332 KB Output is correct
17 Correct 180 ms 169600 KB Output is correct
18 Correct 144 ms 169668 KB Output is correct
19 Execution timed out 6111 ms 227284 KB Time limit exceeded
20 Halted 0 ms 0 KB -