Submission #997395

#TimeUsernameProblemLanguageResultExecution timeMemory
997395doducanhPalembang Bridges (APIO15_bridge)C++14
31 / 100
2098 ms3776 KiB
#include <bits/stdc++.h> using namespace std; #define ii pair<int,int> const int maxn=1e5+7; struct nguoi { int xo,yo,xt,yt; }; nguoi a[maxn]; int k,n; vector<ii>v; vector<int>tmp; long long f(int t) { long long sum=0; for(auto [x,y]:v){ sum+=(abs(x-t)+abs(y-t)+1); } return sum; } void sub1() { long long delt=0; for(int i=1;i<=n;i++){ char xo,xt; cin>>xo>>a[i].yo>>xt>>a[i].yt; a[i].xo=(xo=='B'); a[i].xt=(xt=='B'); if(xo==xt){ delt+=abs(a[i].yt-a[i].yo); } else{ tmp.push_back(a[i].yo); tmp.push_back(a[i].yt); v.push_back({a[i].yo,a[i].yt}); } } int l=0,r=1e9+7; while(r-l>1000){ int m1=l+(r-l)/3; int m2=r-(r-l)/3; if(f(m1)<f(m2)){ r=m2; } else l=m1; } // for(auto [x,y]:v){ // cout<<x<<" "<<y<<"\n"; // } long long ans=LLONG_MAX; for(auto i=l;i<=r;i++){ ans=min(ans,f(i)); // if(f(i)==18)cout<<i; // cout<<f(i)<<"\n"; } cout<<ans+delt; } void sub2() { long long delt=0; for(int i=1;i<=n;i++){ char xo,xt; cin>>xo>>a[i].yo>>xt>>a[i].yt; a[i].xo=(xo=='B'); a[i].xt=(xt=='B'); tmp.push_back(a[i].yo); tmp.push_back(a[i].yt); if(xo==xt){ delt+=abs(a[i].yt-a[i].yo); } else{ v.push_back({a[i].yo,a[i].yt}); } } sort(tmp.begin(),tmp.end()); tmp.erase(unique(tmp.begin(),tmp.end()),tmp.end()); long long ans=LLONG_MAX; for(int i=0;i<tmp.size()-1;i++){ for(int j=i+1;j<tmp.size();j++){ int to=tmp[i],tt=tmp[j]; long long sum=0; for(auto [x,y]:v){ sum+=min((long long)abs(x-to)+abs(y-to)+1,(long long)abs(x-tt)+abs(y-tt)+1); } ans=min(ans,sum); } } cout<<ans+delt; } main() { cin>>k>>n; if(k==1){ sub1(); } else sub2(); return 0; } /* 1 5 B 0 A 4 B 1 B 3 A 5 B 7 B 2 A 6 B 1 A 7 */

Compilation message (stderr)

bridge.cpp: In function 'long long int f(int)':
bridge.cpp:17:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   17 |     for(auto [x,y]:v){
      |              ^
bridge.cpp: In function 'void sub2()':
bridge.cpp:81:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |     for(int i=0;i<tmp.size()-1;i++){
      |                 ~^~~~~~~~~~~~~
bridge.cpp:82:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |         for(int j=i+1;j<tmp.size();j++){
      |                       ~^~~~~~~~~~~
bridge.cpp:85:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   85 |             for(auto [x,y]:v){
      |                      ^
bridge.cpp: At global scope:
bridge.cpp:93:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   93 | main()
      | ^~~~
#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...