Submission #69895

#	Time	Username	Problem	Language	Result	Execution time	Memory
69895		wleung_bvg	Towns (IOI15_towns)	C11	10 / 100	31 ms	2400 KiB

towns

#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 (stderr)

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) {
                            ^~~

• Subtask 1: 0 / 13
• Subtask 2: 0 / 12
• Subtask 3: 0 / 13
• Subtask 4: 10 / 10
• Subtask 5: 0 / 13
• Subtask 6: 0 / 39