| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 69894 | wleung_bvg | Towns (IOI15_towns) | C11 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;
}
int main() {
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
ri(N);
int sub;
ri(sub);
printf("! %d\n", hubDistance(N, sub));
return 0;
}