Submission #600247

#	Time	Username	Problem	Language	Result	Execution time	Memory
600247		leaked	Towns (IOI15_towns)	C++17	61 / 100	92 ms	1408 KiB

towns

#include <bits/stdc++.h>
#include "towns.h"

#define f first
#define s second
#define m_p make_pair
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define pw(x) (1LL<<(x))
#define sz(x) (int)(x).size()
#define vec vector

using namespace std;
template <class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
template <class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}

typedef long long ll;
typedef pair<int,int> pii;

map<pii,int> mp;
int dist(int i,int j){
    if(i==j || mp.count({i,j}))
        return mp[{i,j}];
    mp[{i,j}]=mp[{j,i}]=getDistance(i,j);
    return mp[{i,j}];
}
int n;
int getcnt(int sub){
    if(sub==5)
        return 2;
    if(sub==1 || sub==3)
        return n;
    return 0;
}
int hubDistance(int n, int sub){
    int v,u;
    ::n=n;
    mp.clear();
    srand(n*sub);
    int ft=rand()%n;
    vec<int> r(n);
    {
//        vec<int> r(n);
        for(int i=0;i<n;i++) r[i]=dist(ft,i);
        v=max_element(all(r))-r.begin();
    }

    vec<int> r1(n),r2(n);
    for(int i=0;i<n;i++) r1[i]=dist(v,i);

    u=max_element(all(r1))-r1.begin();



    vec<pii> cand;

    vec<int> d1(n),d2(n);
    vec<int> rasts;
    vec<int> pref,suf;

    vec<int> c1,c2;

    map<int,int> mp;
    map<int,int> cnt;


    for(int i=0;i<n;i++){
//        r2[i]=dist(u,i);

        int s=(r1[i]+r1[ft]-r[i]);

        assert((s%2)==0);
        s/=2;
        d2[i]=s;

        d1[i]=r1[i]-s;

        umax(mp[d2[i]],d1[i]);
        ++cnt[d2[i]];

    }
    for(auto &z : mp)
        rasts.pb(z.f),pref.pb(z.s);

    for(auto &z : cnt) c1.pb(z.s);


    suf=pref;c2=c1;

    for(int i=1;i<sz(rasts);i++)
        umax(pref[i],pref[i-1]+rasts[i]-rasts[i-1]),c1[i]+=c1[i-1];
    for(int i=sz(rasts)-2;i>=0;i--)
        umax(suf[i],suf[i+1]+rasts[i+1]-rasts[i]),c2[i]+=c2[i+1];


    int mn=1e9;
    for(int i=0;i<sz(rasts);i++){
        umin(mn,max(pref[i],suf[i]));
    }
    if(sub==4){
        int ok=0;
        for(int i=0;i<sz(rasts);i++){
            if(max(pref[i],suf[i])!=mn) continue;
            int f=(i?c1[i-1]:0),s=(i+1==sz(rasts)?0:c2[i+1]);
            int t=c1[i]-f;
            if(f<=(n/2) && s<=(n/2) && t<=(n/2))
                ok=1;
        }
        if(!ok) mn*=-1;
        return mn;
    }
    int ct=0;

    vec<int> cands={ft,v};

    for(int it=0;it<=getcnt(sub);it++){
        int x=rand()%n;
        cands.pb(x);
    }

//    vec<vec<int>> dsts;
//    for(auto &x : cands){
//        dsts.pb(vec<int>());
//        for(int y=0;y<n;y++){
//            dsts.back().pb(dist(x,y));
////        }
//    }

    int ok=0;
    for(int i=0;i<sz(rasts);i++){
        if(max(pref[i],suf[i])==mn){
            ++ct;
            /// check him
            int mok=1;
            for(int f=0;f<sz(cands);f++){
                int x=cands[f];
                int here=0;
                for(int y=0;y<n;y++){
                    int my=d1[x]+abs(d2[x]-rasts[i]);
                    int his=d1[y]+abs(d2[y]-rasts[i]);

                    assert((my+his)>=dist(x,y));

                    if((my+his)!=dist(x,y))
                        ++here;

                    if(here>(n/2)){
                        break;
                    }
                }
//                cout<<"WI "<<here<<' '<<(n/2)<<endl;
                if(here>(n/2))
                    mok=0;
            }
            ok|=mok;
        }
    }
//    cout<<"OK "<<ok<<endl;
    if(!ok) mn*=-1;
//    cout<<"W "<<mn<<endl;
    return mn;
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:36:21: warning: declaration of 'n' shadows a global declaration [-Wshadow]
   36 | int hubDistance(int n, int sub){
      |                 ~~~~^
towns.cpp:28:5: note: shadowed declaration is here
   28 | int n;
      |     ^
towns.cpp:46:30: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   46 |         v=max_element(all(r))-r.begin();
      |           ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~
towns.cpp:52:27: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   52 |     u=max_element(all(r1))-r1.begin();
      |       ~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
towns.cpp:64:18: warning: declaration of 'mp' shadows a global declaration [-Wshadow]
   64 |     map<int,int> mp;
      |                  ^~
towns.cpp:21:14: note: shadowed declaration is here
   21 | map<pii,int> mp;
      |              ^~
towns.cpp:37:11: warning: variable 'u' set but not used [-Wunused-but-set-variable]
   37 |     int v,u;
      |           ^

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