| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 69895 |
2018-08-21T20:37:32 Z |
wleung_bvg |
Towns (IOI15_towns) |
C |
|
31 ms |
2400 KB |
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <string.h>
#include <stdbool.h>
#include <limits.h>
#include <time.h>
#include <assert.h>
#include <stdarg.h>
#include <stddef.h>
#include "towns.h"
#define INT_INF 0x3f3f3f3f
#define LL_INF 0x3f3f3f3f3f3f3f3f
#define EPS 1e-9
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)=min((a),(b)))
#define MAX(a,b) ((a)=max((a),(b)))
#define For(i,a,b) for(int i=(a);i<(b);i++)
#define FOR(i,b) For(i,0,b)
#define Rev(i,a,b) for(int i=(a);i>(b);i--)
#define REV(i,a) Rev(i,a,-1)
typedef long long ll;
typedef long double ld;
typedef unsigned int uint;
typedef unsigned long long ull;
#define _bufferSize 4096
#define _maxNumLength 128
char _inputBuffer[_bufferSize+1],*_inputPtr=_inputBuffer,_c,_sign;int _cur;
#define _peekchar() (*_inputPtr?*_inputPtr:(_inputBuffer[fread(_inputPtr=_inputBuffer,1,_bufferSize,stdin)]='\0',*_inputPtr))
#define _getchar() getchar()
#define _hasNext() (*_inputPtr||!feof(stdin))
#define _readSignAndNum(x) do{(x)=_getchar();}while((x)<=' ');_sign=(x)=='-';if(_sign)(x)=_getchar();for((x)-='0';(_c=_getchar())>='0';(x)=(x)*10+_c-'0')
#define _readFloatingPoint(x,T) for(T _div=1.0;(_c=_getchar())>='0';(x)+=(_c-'0')/(_div*=10))
#define rc(x) do{do{(x)=_getchar();}while((x)<=' ');}while(0)
#define ri(x) do{_readSignAndNum(x);if(_sign)(x)=-(x);}while(0)
#define rd(x) do{_readSignAndNum(x);if(_c=='.')_readFloatingPoint(x,double);if(_sign)(x)=-(x);}while(0)
#define rld(x) do{_readSignAndNum(x);if(_c=='.')_readFloatingPoint(x,ld);if(_sign)(x)=-(x);}while(0)
#define rcs(x) do{_cur=0;do{_c=_getchar();}while(_c<=' ');do{(x)[_cur++]=_c;}while((_c=_getchar())>' ');(x)[_cur]='\0';}while(0)
#define rcln(x) do{_cur=0;do{_c=_getchar();}while(_c<=' ');do{(x)[_cur++]=_c;}while((_c=_getchar())>=' ');(x)[_cur]='\0';}while(0)
int hasNext(){while(_hasNext()&&_peekchar()<=' ')_getchar();return _hasNext();}
#define MAXN 110
int N, distRoot[MAXN], distDiam[MAXN], distPath[MAXN], check[MAXN], checkSz = 0, neq[MAXN], candidates[MAXN], candidatesSz = 0;
// int getDistance(int i, int j) {
// assert(0 <= i && i < N);
// assert(0 <= j && j < N);
// printf("? %d %d\n", i, j);
// fflush(stdout);
// int ans;
// ri(ans);
// return ans;
// }
int qcnt = 0;
int query(int i, int j) {
if (++qcnt > (7 * N + 1) / 2) assert(0);
return getDistance(i, j);
}
int hasMajority(int d) {
int lt = 0, gt = 0, k = 0, cnt = 0;
checkSz = candidatesSz = 0;
FOR(i, N) {
int cmp = distDiam[i] - distPath[i] - d;
if (cmp < 0) lt++;
else if (cmp > 0) gt++;
else check[checkSz++] = i;
}
if (checkSz == 0 || lt > N / 2 || gt > N / 2) return 1;
FOR(i, checkSz) {
if (cnt == 0) {
cnt++;
candidates[candidatesSz++] = k = i;
} else if (neq[i] = (query(check[i], check[k]) != distPath[check[i]] + distPath[check[k]])) cnt++;
else cnt--;
}
cnt = (cnt + checkSz - k) / 2;
FOR(i, candidatesSz - 1) {
if (query(check[candidates[i]], check[k]) != distPath[check[candidates[i]]] + distPath[check[k]]) cnt += (candidates[i + 1] - candidates[i]) / 2;
else For(j, candidates[i] + 1, candidates[i + 1]) if (!neq[j] && query(check[j], check[k]) != distPath[check[j]] + distPath[check[k]]) cnt++;
}
return cnt > N / 2;
}
int hubDistance(int n, int sub) {
qcnt = 0;
N = n;
int diamV = 0, maxDist = distRoot[0] = 0, minPathDist = INT_INF;
For(i, 1, N) {
if (maxDist < (distRoot[i] = query(0, i))) {
maxDist = distRoot[i];
diamV = i;
}
}
distDiam[diamV] = 0;
distDiam[0] = maxDist;
For(i, 1, N) if (i != diamV) MAX(maxDist, distDiam[i] = query(diamV, i));
distPath[0] = distPath[diamV] = 0;
For(i, 1, N) if (i != diamV) MIN(minPathDist, abs(maxDist - 2 * (distDiam[i] - (distPath[i] = (distRoot[i] + distDiam[i] - distDiam[0]) / 2))));
return (hasMajority((maxDist + minPathDist) / 2) && (minPathDist == 0 || hasMajority((maxDist - minPathDist) / 2)) ? -1 : 1) * (maxDist + minPathDist) / 2;
}
Compilation message
towns.c: In function 'hasMajority':
towns.c:80:20: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
} else if (neq[i] = (query(check[i], check[k]) != distPath[check[i]] + distPath[check[k]])) cnt++;
^~~
towns.c: In function 'hubDistance':
towns.c:91:28: warning: unused parameter 'sub' [-Wunused-parameter]
int hubDistance(int n, int sub) {
^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
632 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
5 ms |
868 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
996 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
31 ms |
1872 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
7 ms |
2168 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
5 ms |
2400 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
