Submission #622564

#	Time	Username	Problem	Language	Result	Execution time	Memory
622564		Dremix10	Wiring (IOI17_wiring)	C++17	0 / 100	131 ms	262144 KiB

wiring

#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);
				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;
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:132:21: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  132 |     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;
      |          ^

• Subtask 1: 0 / 7
• Subtask 2: 0 / 13
• Subtask 3: 0 / 10
• Subtask 4: 0 / 25
• Subtask 5: 0 / 45