Submission #623201

#	Time	Username	Problem	Language	Result	Execution time	Memory
623201		Dremix10	Wiring (IOI17_wiring)	C++17	0 / 100	1088 ms	284 KiB

wiring

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
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;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution <ll> distr;
ll rnd(ll x, ll y){return distr(rng)%(y-x+1)+x;}

vector<int> R,B;
vector<int> vr,vb;
ll ans = INF,res = 0;

void solveB(int i){
	if(i == B.size()){
		ans = min(ans,res);
		return;
	}
	int j;
	if(vb[i] > 0)solveB(i+1);
	else{
		for(j=0;j<R.size();j++){
			res += abs(R[j] - B[i]);
			vr[j] ++;
			vb[i] ++;
			solveB(i+1);
			res -= abs(R[j] - B[i]);
			vr[j] --;
			vb[i] --;
		}
	}	
}

void solveR(int i){
	if(i == R.size()){
		solveB(0);
		return;
	}
	int j;
	if(vr[i] > 0)solveR(i+1);
	else{
		for(j=0;j<B.size();j++){
			res += abs(R[i] - B[j]);
			vr[i] ++;
			vb[j] ++;
			solveR(i+1);
			res -= abs(R[i] - B[j]);
			vr[i] --;
			vb[j] --;
		}
	}	
}

long long min_total_length(std::vector<int> r, std::vector<int> b) {
	R = r;
	B = b;
	vr.assign(r.size(),0);
	vb.assign(b.size(),0);

	solveR(0);

	return ans;
}

Compilation message (stderr)

wiring.cpp: In function 'void solveB(int)':
wiring.cpp:36:7: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |  if(i == B.size()){
      |     ~~^~~~~~~~~~~
wiring.cpp:43:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |   for(j=0;j<R.size();j++){
      |           ~^~~~~~~~~
wiring.cpp: In function 'void solveR(int)':
wiring.cpp:56:7: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |  if(i == R.size()){
      |     ~~^~~~~~~~~~~
wiring.cpp:63:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |   for(j=0;j<B.size();j++){
      |           ~^~~~~~~~~

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