Submission #151450

#	Time	Username	Problem	Language	Result	Execution time	Memory
151450		Bodo171	Towns (IOI15_towns)	C++14	25 / 100	21 ms	888 KiB

towns

//I have doubts about the grader so I'll test it with a good solution
//the author of this code is ainta but it's a bit modified

#include "towns.h"
#include<algorithm>
using namespace std;
#define pii pair<int,int>
#define X first
#define Y second

#define N_ 120
#define INF 999999999

int D1[N_], D2[N_], ddis, n, p1, p2;
pii w[15][N_];
bool chk[15][N_];
int v[N_], ckk;

bool Same(int a, int b){
    int d = getDistance(a,b);
    if(d!=D2[a]+D2[b]-ddis*2)return true;
    return false;
}

pii Do(int pv, int cnt){
    int i, cc = 0, t;
    if(cnt == 1)return w[pv][0];
    for(i=0;i<cnt/2;i++){
        chk[pv][i]=false;
        if(Same(w[pv][i*2].X,w[pv][i*2+1].X)){
            w[pv+1][cc] = w[pv][i*2];
            w[pv+1][cc].Y += w[pv][i*2+1].Y;
            cc++;
        }
        else{
            chk[pv][i]=true;
            if(w[pv][i*2].Y>w[pv][i*2+1].Y){
                w[pv+1][cc] = w[pv][i*2];
                w[pv+1][cc].Y -= w[pv][i*2+1].Y;
                cc++;
            }
            else if(w[pv][i*2].Y<w[pv][i*2+1].Y){
                w[pv+1][cc] = w[pv][i*2+1];
                w[pv+1][cc].Y -= w[pv][i*2].Y;
                cc++;
            }
        }
    }
    if(cnt%2==1){
        w[pv+1][cc] = w[pv][cnt-1];
        cc++;
    }
    pii r = pii(0,0);
    if(cc)r = Do(pv+1,cc);
    if(r.Y==0)return r;
    for(i=0;i<cnt/2;i++){
        if(chk[pv][i]){
            t = min(w[pv][i*2].Y,w[pv][i*2+1].Y);
            if(Same(w[pv][i*2].X,r.X))r.Y+=t;
            else r.Y-=t;
            if(Same(w[pv][i*2+1].X,r.X))r.Y+=t;
            else r.Y-=t;
        }
    }
    if(r.Y>0)return r;
    return pii(0,0);
}

bool Pos(int N, int d){
    int i, c1 = 0, c2 = 0, t, cnt = 0;
    for(i=0;i<N;i++){
        t = D2[i] - (D1[i]+D2[i]-D1[p1])/2;
        if(t < d) c1++;
        else if(t > d) c2++;
        else w[0][cnt++] = pii(i,1);
    }
    if(c1>N/2||c2>N/2)return false;
    if(ckk)return false;
    ckk = 1;
    ddis = d;
    if((Do(0,cnt).Y + cnt) > N)return false;
    return true;
}

int hubDistance(int N, int sub) {
    n = N;
    int i, M = -1, R, t, dd;
    D1[0]=0;
    for(i=1;i<N;i++){
        D1[i] = getDistance(0,i);
        if(M<D1[i])M=D1[i],p1=i;
    }
    M=-1;
    D2[p1]=0;
    for(i=0;i<N;i++){
        if(i!=p1) D2[i] = getDistance(p1,i);
        if(M<D2[i])M=D2[i],p2=i;
    }
    dd = (D1[p1] + D2[p2] - D1[p2])/2;
    R = INF;
    for(i=0;i<N;i++){
        t = D2[i]-(D1[i]+D2[i]-D1[p1])/2;
        if(t <= dd){
            R = min(R, max(t,D2[p2]-t));
        }
    }
    return R;
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:85:28: warning: unused parameter 'sub' [-Wunused-parameter]
 int hubDistance(int N, int sub) {
                            ^~~

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