oj.uz

답안 #429703

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
429703 2021-06-16T08:50:30 Z 송준혁(#7525) Power plants (CPSPC17_power) C++17
0 / 100
 265 ms 341804 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=1e18;
	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:88:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   88 |   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:84:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
Main.cpp:85:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |  for (int i=1; i<=N; i++) scanf("%lld %lld", &X[i], &Y[i]);
      |                           ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 123 ms 168644 KB Output is correct
2 Correct 111 ms 168648 KB Output is correct
3 Correct 116 ms 168740 KB Output is correct
4 Correct 113 ms 168712 KB Output is correct
5 Correct 113 ms 168760 KB Output is correct
6 Runtime error 265 ms 341804 KB Execution killed with signal 8
7 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 123 ms 168644 KB Output is correct
2 Correct 111 ms 168648 KB Output is correct
3 Correct 116 ms 168740 KB Output is correct
4 Correct 113 ms 168712 KB Output is correct
5 Correct 113 ms 168760 KB Output is correct
6 Runtime error 265 ms 341804 KB Execution killed with signal 8
7 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 123 ms 168644 KB Output is correct
2 Correct 111 ms 168648 KB Output is correct
3 Correct 116 ms 168740 KB Output is correct
4 Correct 113 ms 168712 KB Output is correct
5 Correct 113 ms 168760 KB Output is correct
6 Runtime error 265 ms 341804 KB Execution killed with signal 8
7 Halted 0 ms 0 KB -