제출 #622570

#제출 시각아이디문제언어결과실행 시간메모리
622570Dremix10전선 연결 (IOI17_wiring)C++17
0 / 100
121 ms262144 KiB
#include "wiring.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> pi; typedef pair<ll,ll> pl; #define F first #define S second #define all(x) (x).begin(),(x).end() #ifdef dremix #define p(x) cerr<<#x<<" = "<<x<<endl; #define p2(x,y) cerr<<#x<<" , "<<#y<<" = "<<x<<" , "<<y<<endl; #define pp(x) cerr<<#x<<" = "<<x.F<<"-"<<x.S<<endl; #define pv(x) cerr<<#x<<" = {";for(auto v : x)cerr<<v<<", ";cerr<<"}"<<endl; #define ppv(x) cerr<<#x<<" = {";for(auto v : x)cerr<<v.F<<"-"<<v.S<<", ";cerr<<"}"<<endl; #else #define p(x) {} #define p2(x,y) {} #define pp(x) {} #define pv(x) {} #define ppv(x) {} #endif const int N = 3e5+5; const int MOD = 1e9+7; const ll INF = 1e18+5; void solve(int i){ } long long min_total_length(std::vector<int> r, std::vector<int> b) { int i,j,k; int n = r.size(); int m = b.size(); ll ans = 0; int cr[n] = {}; int cb[m] = {}; bool v[n][m] = {}; vector<pi> arr; for(i=0;i<n;i++){ int idx = -1; for(j=0;j<m;j++){ if(idx == -1 || abs(r[i]-b[j]) < abs(r[i]-b[idx])) idx = j; } cr[i]++; cb[idx]++; v[i][idx] = true; arr.push_back({i,idx}); ans += abs(r[i] - b[idx]); } for(i=0;i<m;i++){ int idx = -1; for(j=0;j<n;j++){ if(idx == -1 || abs(r[j]-b[i]) < abs(b[i]-r[idx])) idx = j; } if(v[idx][i])continue; cb[i]++; cr[idx]++; v[idx][i] = true; arr.push_back({idx,i}); ans += abs(b[i] - r[idx]); } bool flag = true; //vector<pi> neo; while(flag){ flag = false; vector<pi> neo; ppv(arr) p(ans) pv(cr) pv(cb) for(auto &x : arr){ //neo.push_back(x); if(v[x.F][x.S] == false)continue; if(cr[x.F] > 1 && cb[x.S] > 1){ cr[x.F] --; cb[x.S] --; ans -= abs(r[x.F] - b[x.S]); v[x.F][x.S] = false; //neo.pop_back(); continue; } if(cr[x.F] == 1 && cb[x.S] == 1){ //neo.push_back(x); int idx1 = x.S; for(i=0;i<m;i++){ if(abs(r[x.F]-b[i]) < abs(r[x.F]-b[idx1])) idx1 = i; } ///prove? if(idx1 == x.S)continue; int idx2 = x.F; for(i=0;i<n;i++){ if(abs(r[i]-b[x.S]) < abs(r[idx2]-b[x.S])) idx2 = i; } ///prove? if(idx2 == x.F)continue; if(abs(r[x.F] - b[x.S]) > abs(r[x.F] - b[idx1]) + abs(r[idx2] - b[x.S])){ cr[idx2] ++; cb[idx1] ++; ans -= abs(r[x.F] - b[x.S]) - abs(r[x.F] - b[idx1]) - abs(r[idx2] - b[x.S]); v[x.F][x.S] = false; v[x.F][idx1] = true; v[idx2][x.S] = true; neo.push_back({x.F,idx1}); neo.push_back({idx2,x.S}); } continue; } if(cr[x.F] == 1){ assert(cb[x.S] > 1); int idx = x.S; for(i=0;i<m;i++){ if(abs(r[x.F]-b[i]) < abs(r[x.F]-b[idx])) idx = i; } if(idx != x.S){ cb[x.S] --; cb[idx] ++; ans -= abs(r[x.F] - b[x.S]) - abs(r[x.F] - b[idx]); v[x.F][x.S] = false; v[x.F][idx] = true; neo.push_back({x.F,idx}); continue; } } else{ assert(cr[x.F] > 1 && cb[x.S] == 1); int idx = x.F; for(i=0;i<n;i++){ if(abs(r[i]-b[x.S]) < abs(r[idx]-b[x.S])) idx = i; } if(idx != x.F){ cr[x.F] --; cr[idx] ++; ans -= abs(r[x.F] - b[x.S]) - abs(r[idx] - b[x.S]); v[x.F][x.S] = false; v[idx][x.S] = true; neo.push_back({idx,x.S}); continue; } } for(auto &y : arr){ if(v[y.F][y.S] == false)continue; if(cr[y.F] == 1 && cb[y.S] == 1 || x==y)continue; if(cr[y.F] > 1 && cb[y.S] > 1)continue; if(cr[x.F] == 1 && cb[y.S] == 1){ if(abs(r[x.F]-b[x.S]) + abs(r[y.F]-b[y.S]) > abs(r[x.F] - b[y.S])){ pp(x) pp(y) cr[y.F]--; cb[x.S]--; ans -= abs(r[x.F]-b[x.S]) + abs(r[y.F]-b[y.S]) - abs(r[x.F] - b[y.S]); v[x.F][x.S] = false; v[y.F][y.S] = false; v[x.F][y.S] = true; neo.push_back({x.F,y.S}); break; } } else if(cb[x.S] == 1 && cr[y.F] == 1){ if(abs(r[x.F]-b[x.S]) + abs(r[y.F]-b[y.S]) > abs(r[y.F] - b[x.S])){ pp(y) pp(x) cr[x.F]--; cb[y.S]--; ans -= abs(r[x.F]-b[x.S]) + abs(r[y.F]-b[y.S]) - abs(r[y.F] - b[x.S]); v[x.F][x.S] = false; v[y.F][y.S] = false; v[y.F][x.S] = true; neo.push_back({y.F,x.S}); break; } } } } vector<pi> temp; for(auto &x : arr){ if(v[x.F][x.S] == false){ flag = true; continue; } temp.push_back(x); } for(auto &x : neo){ flag = true; temp.push_back(x); } arr = temp; } return ans; }

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

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:157:21: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  157 |     if(cr[y.F] == 1 && cb[y.S] == 1 || x==y)continue;
      |        ~~~~~~~~~~~~~^~~~~~~~~~~~~~~
wiring.cpp:33:10: warning: unused variable 'k' [-Wunused-variable]
   33 |  int i,j,k;
      |          ^
#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...