제출 #868137

#제출 시각아이디문제언어결과실행 시간메모리
868137waldi도시들 (IOI15_towns)C++17
61 / 100
17 ms1112 KiB
#include "towns.h" #include <bits/stdc++.h> #define FOR(i,p,k) for(int i=(p);i<=(k);++i) #define REP(i,n) FOR(i,0,(n)-1) #define fi first #define se second #define debug(a) cerr << #a << ": " << a << "\n"; using namespace std; typedef pair<int, int> pii; int hubDistance(int n, int sub){ vector odpowiedz(110, vector(110, -1)); auto zapytaj = [&](int i, int j){ if(i > j) swap(i, j); if(odpowiedz[i][j]<0) odpowiedz[i][j] = getDistance(i, j); return odpowiedz[i][j]; }; int a = 0; vector<int> od0(n, 0); FOR(i, 1, n-1){ od0[i] = zapytaj(0, i); if(od0[i] > od0[a]) a = i; } int b = 0; vector<int> oda(n, 0); REP(i, n) if(i != a){ oda[i] = zapytaj(a, i); if(oda[i] > oda[b]) b = i; } int sred = oda[b]; vector<int> odb(n, 0); REP(i, n) if(i != b) odb[i] = zapytaj(b, i); auto odsred = [&](int i){ return (oda[i]+odb[i]-sred)>>1; }; auto gdzie = [&](int i){ return oda[i]-odsred(i); }; auto odleglosc = [&](int i, int poz){ return odsred(i) + abs(poz-gdzie(i)); }; set<int> secik; REP(i, n) secik.emplace(gdzie(i)); int wyn = sred+1, poz = -1, jestgit = 0; for(int off : secik){ int maks = 0; REP(i, n) maks = max(maks, odleglosc(i, off)); int lewo = 0, prawo = 0; REP(i, n){ int odla = gdzie(i); if(odla < off) ++lewo; if(odla > off) ++prawo; } int terazgit = max(lewo, prawo) <= n/2; if(maks < wyn) wyn = maks, poz = off, jestgit = terazgit; else if(maks == wyn && !jestgit) poz = off, jestgit = terazgit; } if(sub <= 2) return wyn; if(sub == 4){ int lewo = 0, prawo = 0, ja = 0; REP(i, n){ int odla = gdzie(i); if(odla < poz) ++lewo; if(odla == poz) ++ja; if(odla > poz) ++prawo; } bool zle = 0; zle |= lewo > n/2; zle |= prawo > n/2; zle |= ja > n/2;// wiem to jest jedno poddrzewo if(zle) wyn = -wyn; return wyn; } auto rowne = [&](int x, int y){ return zapytaj(x, y) < odleglosc(x, poz)+odleglosc(y, poz); }; int lider = 0, licznik = 1; FOR(i, 1, n-1){ if(rowne(lider, i)) ++licznik; else --licznik; if(!licznik) lider = i, licznik = 1; } int ile = 0; REP(i, n) if(rowne(i, lider)) ++ile; if(ile > n/2) wyn = -wyn; return wyn; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...