# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
600247 |
2022-07-20T14:59:01 Z |
leaked |
Towns (IOI15_towns) |
C++17 |
|
92 ms |
1408 KB |
#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
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;
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
92 ms |
1408 KB |
Output is correct |
2 |
Correct |
81 ms |
1268 KB |
Output is correct |
3 |
Correct |
1 ms |
300 KB |
Output is correct |
4 |
Correct |
80 ms |
1324 KB |
Output is correct |
5 |
Correct |
89 ms |
1396 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
972 KB |
Output is correct |
2 |
Correct |
13 ms |
848 KB |
Output is correct |
3 |
Correct |
18 ms |
468 KB |
Output is correct |
4 |
Correct |
17 ms |
916 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
76 ms |
1336 KB |
Output is correct |
2 |
Correct |
91 ms |
1360 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
90 ms |
1396 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
436 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
484 KB |
Output is correct |
2 |
Correct |
22 ms |
912 KB |
Output is correct |
3 |
Correct |
18 ms |
908 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
19 ms |
340 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |