oj.uz

Submission #429892

# Submission time Handle Problem Language Result Execution time Memory
429892 2021-06-16T10:17:22 Z songc Power plants (CPSPC17_power) C++14
35 / 100
 6000 ms 224044 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 <= 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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 168628 KB Output is correct
2 Correct 141 ms 168648 KB Output is correct
3 Correct 136 ms 168740 KB Output is correct
4 Correct 137 ms 168736 KB Output is correct
5 Correct 127 ms 168792 KB Output is correct
6 Correct 137 ms 168664 KB Output is correct
7 Correct 140 ms 168732 KB Output is correct
8 Correct 131 ms 168724 KB Output is correct
9 Correct 125 ms 168644 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 168628 KB Output is correct
2 Correct 141 ms 168648 KB Output is correct
3 Correct 136 ms 168740 KB Output is correct
4 Correct 137 ms 168736 KB Output is correct
5 Correct 127 ms 168792 KB Output is correct
6 Correct 137 ms 168664 KB Output is correct
7 Correct 140 ms 168732 KB Output is correct
8 Correct 131 ms 168724 KB Output is correct
9 Correct 125 ms 168644 KB Output is correct
10 Correct 174 ms 169684 KB Output is correct
11 Correct 162 ms 169484 KB Output is correct
12 Correct 168 ms 169408 KB Output is correct
13 Correct 152 ms 169812 KB Output is correct
14 Correct 192 ms 169552 KB Output is correct
15 Correct 175 ms 169100 KB Output is correct
16 Correct 160 ms 169380 KB Output is correct
17 Correct 162 ms 169496 KB Output is correct
18 Correct 178 ms 169512 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 168628 KB Output is correct
2 Correct 141 ms 168648 KB Output is correct
3 Correct 136 ms 168740 KB Output is correct
4 Correct 137 ms 168736 KB Output is correct
5 Correct 127 ms 168792 KB Output is correct
6 Correct 137 ms 168664 KB Output is correct
7 Correct 140 ms 168732 KB Output is correct
8 Correct 131 ms 168724 KB Output is correct
9 Correct 125 ms 168644 KB Output is correct
10 Correct 174 ms 169684 KB Output is correct
11 Correct 162 ms 169484 KB Output is correct
12 Correct 168 ms 169408 KB Output is correct
13 Correct 152 ms 169812 KB Output is correct
14 Correct 192 ms 169552 KB Output is correct
15 Correct 175 ms 169100 KB Output is correct
16 Correct 160 ms 169380 KB Output is correct
17 Correct 162 ms 169496 KB Output is correct
18 Correct 178 ms 169512 KB Output is correct
19 Execution timed out 6116 ms 224044 KB Time limit exceeded
20 Halted 0 ms 0 KB -