제출 #171576

#제출 시각아이디문제언어결과실행 시간메모리
171576Ruxandra985Palembang Bridges (APIO15_bridge)C++14
22 / 100
351 ms28820 KiB
#include <bits/stdc++.h> #define DIMN 100010 using namespace std; vector <long long> vmax[2*DIMN] , vmin[2*DIMN]; set <long long> s; pair <long long,long long> nv[DIMN]; long long p[2*DIMN] , sol_sl[DIMN] , sol_sr[DIMN]; int cmp (pair <long long,long long> a , pair <long long,long long> b){ return a.first + a.second < b.first + b.second; /// sort dupa media aritmetica } long long findd (long long x , long long tot){ long long st , dr , mid; st = 0; dr = tot - 1; while (st <= dr){ mid = (st + dr)/2; if (p[mid] == x) return mid; else if (p[mid] < x) st = mid + 1; else dr = mid - 1; } return -1; } int main() { FILE *fin = stdin; FILE *fout = stdout; long long k , n , elem , tot = 0 , tot2 = 0, i ,p1 , p2 , left , right , poz , j; char c1 , c2; long long sol , base , sl , sr , sum , summ; fscanf (fin,"%lld%lld\n",&k,&n); base = 0; elem = 0; for (i=1;i<=n;i++){ c1 = fgetc(fin); fscanf (fin,"%lld ",&p1); c2 = fgetc(fin); fscanf (fin,"%lld\n",&p2); if (c1 == c2){ base = base + max ( p2 - p1 , p1 - p2 ); } else{ base = base + 1 + max ( p2 - p1 , p1 - p2 ); nv[++elem] = make_pair(min(p1,p2) , max(p1,p2)); p[tot++] = p1; p[tot++] = p2; } } sort ( p , p + tot); tot2 = 0; for (i=0;i<tot;i++){ if (i == 0 || p[i] != p[i-1]) p[tot2++] = p[i]; } tot = tot2; for (i=1;i<=elem;i++){ nv[i].first = findd (nv[i].first , tot); nv[i].second = findd (nv[i].second , tot); p1 = nv[i].first; p2 = nv[i].second; s.insert(p1); s.insert(p2); vmax[max(p1 ,p2)].push_back(min(p1 , p2)); vmin[min(p1 ,p2)].push_back(max(p1 , p2)); } n = elem; if (k == 1){ /// asta e ok left = 0; right = n - vmin[*(s.begin())].size(); sl = 0; sr = 0; for (i=1;i<=n;i++){ if (nv[i].first != *(s.begin())) sr = sr + 2 * ( p[nv[i].first] - p[(*(s.begin()))] ); } sol = 2000000000000000; for (set <long long> :: iterator it = s.begin() ; it != s.end() ;){ poz = (*it); // printf ("%lld ",poz); sol = min(sol , sl + sr); /// acum e timpul sa modific left ul si right ul left = left + vmax[poz].size(); right = right - vmin[poz+1].size(); it++; if (it == s.end()) break; sl += 2 * (p[(*it)] - p[poz]) * left; sr -= 2 * (p[(*it)] - p[poz]) * ( right + vmin[poz+1].size() ); } if (sol == 2000000000000000) sol = 0; fprintf (fout,"%lld" , sol + base); } else { /// aici k = 2 /// construiesti pentru prefixe /// cand faci media primelor i , faci media dintre sumele intre inc si sf /// media aritmetica inc , inc+1 ... sf = media aritmetica inc sf sort (nv + 1 , nv + elem + 1 , cmp); /// sort dupa media aritmetica sum = 0; for (i=1;i<=elem;i++){ /// pt prefixul 1..i de pozitii , daca ai pune pod? sum = sum + nv[i].first + nv[i].second; poz = sum / (2 * i); /// media /// pt podurile 1 ... i cel mai bn e sa pui un pod aici /// calcul summ = 0; for (j=1;j<=i;j++){ if (nv[i].first <= poz && poz <= nv[i].second) continue; else if (nv[i].first < poz && nv[i].second < poz) summ = summ + 2 * (poz - nv[i].second); else summ = summ + 2 * (nv[i].first - poz); } sol_sl[i] = summ; poz = poz + 1; /// inca o varianta de medie pt ca nu se imparte exact? /// calcul summ = 0; for (j=1;j<=i;j++){ if (nv[i].first <= poz && poz <= nv[i].second) continue; else if (nv[i].first < poz && nv[i].second < poz) summ = summ + 2 * (poz - nv[i].second); else summ = summ + 2 * (nv[i].first - poz); } sol_sl[i] = min(sol_sl[i] , summ); } sum = 0; for (i=elem;i;i--){ /// pt prefixul 1..i de pozitii , daca ai pune pod? sum = sum + nv[i].first + nv[i].second; poz = sum / (2 * (elem - i + 1)); /// media /// pt podurile 1 ... i cel mai bn e sa pui un pod aici /// calcul summ = 0; for (j=n;j>i;j--){ if (nv[i].first <= poz && poz <= nv[i].second) continue; else if (nv[i].first < poz && nv[i].second < poz) summ = summ + 2 * (poz - nv[i].second); else summ = summ + 2 * (nv[i].first - poz); } sol_sr[i] = summ; poz = poz + 1; /// inca o varianta de medie pt ca nu se imparte exact? /// calcul summ = 0; for (j=n;j>i;j--){ if (nv[i].first <= poz && poz <= nv[i].second) continue; else if (nv[i].first < poz && nv[i].second < poz) summ = summ + 2 * (poz - nv[i].second); else summ = summ + 2 * (nv[i].first - poz); } sol_sr[i] = min(sol_sr[i] , summ); } /// conatruiesti pentru sufixe sol = 2000000000000; sol = min (sol_sl[elem] , sol_sr[1]); for (i = 1 ; i < elem ; i++){ sol = min(sol , sol_sl[poz] + sol_sr[poz + 1]); } if (sol == 2000000000000) sol = 0; fprintf (fout,"%lld" , sol + base); } return 0; }

컴파일 시 표준 에러 (stderr) 메시지

bridge.cpp: In function 'int main()':
bridge.cpp:37:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     fscanf (fin,"%lld%lld\n",&k,&n);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bridge.cpp:42:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf (fin,"%lld ",&p1);
         ~~~~~~~^~~~~~~~~~~~~~~~~
bridge.cpp:44:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf (fin,"%lld\n",&p2);
         ~~~~~~~^~~~~~~~~~~~~~~~~~
#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...