Submission #623304

#	Time	Username	Problem	Language	Result	Execution time	Memory
623304		Dremix10	Wiring (IOI17_wiring)	C++17	0 / 100	461 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;
	int cnt=0;
	while(flag){
		cnt++;
		if(cnt > 100)break;
		flag = false;
		vector<pi> neo;
		p("1--------")
		ppv(arr)
		p(ans)
		pv(cr)
		pv(cb)
		for(auto &x : arr){
			pp(x)
			//ppv(arr)
			p(ans)
			pv(cr)
			pv(cb)
			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;
				break;
			}
			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?
				pp(x)
				p(idx1)
				if(idx1 != x.S){
					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?
					p(idx2)
					if(idx2 != x.F){

						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});
							break;
						}
					}
				}
			}
			
			if(cr[x.F] == 1 && 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});
					break;
				}
			}
			else if(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});
					break;
				}
			}
			bool nxt = false;
			for(auto &y : arr){
				if(v[y.F][y.S] == false)continue;
				if(v[x.F][x.S] == false)break;
				if(x == y)continue;
				ll temp1 =  abs(r[x.F] - b[x.S]) + abs(r[y.F] - b[y.S]);
				ll temp2 = abs(r[x.F] - b[y.S]) + abs(r[y.F] - b[x.S]);
				if(temp1 - temp2 > 0){
					pp(x)
					pp(y)
					ans -= temp1 - temp2;
					v[x.F][x.S] = false;
					v[y.F][y.S] = false;
					v[x.F][y.S] = true;
					v[y.F][x.S] = true;
					neo.push_back({x.F,y.S});
					neo.push_back({y.F,x.S});
					nxt = true;
					break;
				}
				else if(cr[x.F] == 1 && cb[x.S] > 1){
					int idx = y.S;
					for(i=0;i<m;i++){
						if(abs(r[y.F]-b[i]) < abs(r[y.F]-b[idx]))
							idx = i;
					}
					
					if(temp1 - abs(r[x.F] - b[y.S]) - abs(r[y.F] - b[idx]) > 0){
						p2(temp1,idx)
						pp(y)
						assert(idx != y.S);
						ans -= temp1;
						v[x.F][x.S] = false;
						v[y.F][y.S] = false;
						/// cnt do
						cb[x.S] --;
						cb[idx] ++;

						v[x.F][y.S] = true;
						v[y.F][idx] = true;
						neo.push_back({x.F,y.S});
						neo.push_back({y.F,idx});
						ans += abs(r[x.F] - b[y.S]);
						ans += abs(r[y.F] - b[idx]);
						nxt = true;
						break;
					}
				}
				else if(cr[x.F] > 1 && cb[x.S] == 1){
					int idx = y.F;
					for(i=0;i<n;i++){
						if(abs(r[i]-b[y.S]) < abs(r[idx]-b[y.S]))
							idx = i;
					}
					ll temp2 = abs(r[y.F] - b[x.S]) + abs(r[idx] - b[y.S]);
					
					if(temp1 - temp2 > 0){
						p2(temp1,idx)
						pp(y)
						assert(idx != y.F);
						ans -= temp1;
						v[x.F][x.S] = false;
						v[y.F][y.S] = false;
						/// cnt do
						cr[x.F] --;
						cr[idx] ++;

						v[y.F][x.S] = true;
						v[idx][y.S] = true;
						neo.push_back({y.F,x.S});
						neo.push_back({idx,y.S});
						ans += temp2;
						nxt = true;
						break;
					}
					else if(cb[y.S] > 1 && temp1 - temp2 + abs(r[idx] - b[y.S]) > 0){
						ans -= temp1;
						v[x.F][x.S] = false;
						v[y.F][y.S] = false;

						cr[x.F]--;
						cb[y.S]--;

						v[y.F][x.S] = true;
						neo.push_back({y.F,x.S});
						ans += temp2 - abs(r[idx] - b[y.S]);
						nxt = true;
						break;
					}
				}
			}
			if(nxt)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: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