oj.uz

Submission #429690

# Submission time Handle Problem Language Result Execution time Memory
429690 2021-06-16T08:45:45 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];
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;
	int cnt=0;
	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]){
			cnt++;
			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;
			}
		}
	}
	assert(cnt < 42);
	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:46:20: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   46 |  for (register int dx=-2; dx<=2; dx++) for (register int dy=-2; dy<=2; dy++){
      |                    ^~
Main.cpp:46:58: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   46 |  for (register int dx=-2; dx<=2; dx++) for (register int dy=-2; dy<=2; dy++){
      |                                                          ^~
Main.cpp: In function 'int main()':
Main.cpp:91:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   91 |   LL m = lo+hi>>1;
      |          ~~^~~
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", ansX.size());
      |          ~^     ~~~~~~~~~~~
      |           |              |
      |           int            std::vector<int>::size_type {aka long unsigned int}
      |          %ld
Main.cpp:104:11: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wformat=]
  104 |  printf("%d\n", ansY.size());
      |          ~^     ~~~~~~~~~~~
      |           |              |
      |           int            std::vector<int>::size_type {aka long unsigned int}
      |          %ld
Main.cpp:87:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
Main.cpp:88:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |  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 168644 KB Output is correct
2 Correct 110 ms 168872 KB Output is correct
3 Correct 113 ms 168856 KB Output is correct
4 Correct 113 ms 168648 KB Output is correct
5 Correct 129 ms 168652 KB Output is correct
6 Correct 108 ms 168644 KB Output is correct
7 Correct 111 ms 168700 KB Output is correct
8 Correct 109 ms 168804 KB Output is correct
9 Correct 109 ms 168656 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 168644 KB Output is correct
2 Correct 110 ms 168872 KB Output is correct
3 Correct 113 ms 168856 KB Output is correct
4 Correct 113 ms 168648 KB Output is correct
5 Correct 129 ms 168652 KB Output is correct
6 Correct 108 ms 168644 KB Output is correct
7 Correct 111 ms 168700 KB Output is correct
8 Correct 109 ms 168804 KB Output is correct
9 Correct 109 ms 168656 KB Output is correct
10 Correct 148 ms 169712 KB Output is correct
11 Correct 138 ms 169568 KB Output is correct
12 Correct 139 ms 169368 KB Output is correct
13 Correct 147 ms 169888 KB Output is correct
14 Correct 162 ms 169796 KB Output is correct
15 Correct 125 ms 169192 KB Output is correct
16 Correct 151 ms 169560 KB Output is correct
17 Correct 148 ms 169540 KB Output is correct
18 Correct 142 ms 169736 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 168644 KB Output is correct
2 Correct 110 ms 168872 KB Output is correct
3 Correct 113 ms 168856 KB Output is correct
4 Correct 113 ms 168648 KB Output is correct
5 Correct 129 ms 168652 KB Output is correct
6 Correct 108 ms 168644 KB Output is correct
7 Correct 111 ms 168700 KB Output is correct
8 Correct 109 ms 168804 KB Output is correct
9 Correct 109 ms 168656 KB Output is correct
10 Correct 148 ms 169712 KB Output is correct
11 Correct 138 ms 169568 KB Output is correct
12 Correct 139 ms 169368 KB Output is correct
13 Correct 147 ms 169888 KB Output is correct
14 Correct 162 ms 169796 KB Output is correct
15 Correct 125 ms 169192 KB Output is correct
16 Correct 151 ms 169560 KB Output is correct
17 Correct 148 ms 169540 KB Output is correct
18 Correct 142 ms 169736 KB Output is correct
19 Execution timed out 6075 ms 227284 KB Time limit exceeded
20 Halted 0 ms 0 KB -