Submission #390221

#	Time	Username	Problem	Language	Result	Execution time	Memory
390221		mehrdad_sohrabi	Wiring (IOI17_wiring)	C++14	100 / 100	69 ms	10176 KiB

wiring

#include <bits/stdc++.h>
#include "wiring.h"
/// 500 485 462 A4
using namespace std;
typedef long long int ll;
typedef complex<double> point;
typedef long double ld;
#define pb push_back
#define pii pair < ll , ll >
#define F first
#define S second
//#define endl '\n'
#define int long long
#define sync ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#define kill(x) return cout<<x<<'\n', 0;
const int N=2e5+100,inf=(ll)1e15;
ll dp[N];
ll par[N];
vector <pii> a;
ll solve(ll l,ll r,ll L,ll R){
    ll zz=0;
    if (l>0) zz=par[l-1];
    ll ans=-(par[r]-zz)+par[R]-par[L-1];
    ll z=r-l+1;
    ll t=R-L+1;
    if (z<t){
        ans-=(t-z)*a[r].F;
    }
    else{
        ans+=(z-t)*a[L].F;
    }
    return ans;
}
void devide(ll l,ll r,ll L,ll R,ll k){
    if (r<l) return ;
    ll mid=(r+l)/2;
    ll id=L,mx=inf;
    for (int i=L;i<=R;i++){
        ll z=solve(mid,k,k+1,i)+min(dp[i],dp[i+1]);
        if (z<=mx){
            mx=z;
            id=i;
        }
    }
    dp[mid]=mx;
    devide(mid+1,r,L,id,k);
    devide(l,mid-1,id,R,k);
}
long long min_total_length(std::vector<int32_t> r, std::vector<int32_t> b) {
	for (auto u : r){
        a.pb({u,0});
	}
	for (auto u : b){
        a.pb({u,1});
	}
	sort(a.begin(),a.end());
	par[0]=a[0].F;
	for (int i=1;i<a.size();i++){
        par[i]=par[i-1]+a[i].F;
	}
	memset(dp,63,sizeof dp);
	dp[a.size()]=0;
	vector <int> best;
	for (int i=a.size()-2;i>-1;i--){
        ll id=i;
        if (i>0 && a[i-1].S==a[i].S) continue;
        while(id<a.size() && a[id].S==a[i].S) id++;
        if (id==a.size()) continue;
        ll id2=id;
        while(id2<a.size() && a[id2].S==a[id].S) id2++;
       // cout << a[i].F << " " << i << " " << id << " " << id2 << endl;
        /*
        ll ww=i;
        for (int j=id;j<id2;j++){
         //   cout << i << " " << id-1 << " " << j << " " << solve(i,id-1,id,j) << endl;
            dp[i]=min(dp[i],solve(i,id-1,id,j)+min(dp[j],dp[j+1]));
            if (dp[i]==solve(i,id-1,id,j)+min(dp[j],dp[j+1])){
                ww=j;
            }
        }
        best.pb(ww);
        */
       // cout << i << " " << id-1 << " " << id+1 << " " << id2-1 << endl;
        devide(i,id-1,id,id2-1,id-1);
       // cout << i << " " << dp[i] << endl;
	}
	return dp[0];

}
/*
int32_t main() {
	int32_t n, m;
	assert(2 == scanf("%d %d", &n, &m));

	vector<int32_t> r(n), b(m);
	for(int i = 0; i < n; i++)
		assert(1 == scanf("%d", &r[i]));
	for(int i = 0; i < m; i++)
		assert(1 == scanf("%d", &b[i]));

	long long res = min_total_length(r, b);
	printf("%lld\n", res);

	return 0;
}
*/
/*
4 5
1 2 3 7
0 4 5 9 10
*/

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:59:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |  for (int i=1;i<a.size();i++){
      |               ~^~~~~~~~~
wiring.cpp:68:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |         while(id<a.size() && a[id].S==a[i].S) id++;
      |               ~~^~~~~~~~~
wiring.cpp:69:15: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |         if (id==a.size()) continue;
      |             ~~^~~~~~~~~~
wiring.cpp:71:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |         while(id2<a.size() && a[id2].S==a[id].S) id2++;
      |               ~~~^~~~~~~~~

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