Submission #69896

#TimeUsernameProblemLanguageResultExecution timeMemory
69896wleung_bvgTowns (IOI15_towns)C11
49 / 100
30 ms5620 KiB
#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) { 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 (stderr)

towns.c: In function 'hasMajority':
towns.c:79: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:90:28: warning: unused parameter 'sub' [-Wunused-parameter]
 int hubDistance(int n, int sub) {
                            ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...