Submission #59167

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
59167	2018-07-20 21:56:14	TadijaSebez	Wiring (IOI17_wiring)	C++11	100 / 100	95 ms	102528 KiB

wiring

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back
const int N=200050;
const ll inf=1e18;
pair<int,int> a[N];
ll dp[N],f[N];
int last[2],cnt[N];
ll max(ll a, ll b){ return a>b?a:b;}
ll min(ll a, ll b){ return a>b?b:a;}
ll min_total_length(vector<int> r, vector<int> b)
{
  int i,j,n;n=r.size()+b.size();
  for(i=0;i<r.size();i++) a[i+1]=mp(r[i],0);
  for(i=0;i<b.size();i++) a[i+1+r.size()]=mp(b[i],1);
  sort(a+1,a+1+n);a[0].second=2;
  bool ok;ll sum=0;last[0]=last[1]=0;
  for(i=1;i<=n;i++)
  {
    dp[i]=inf;
    if(!last[a[i].second^1]){ last[a[i].second]=i;continue;}
    //printf("%i %i %i\n",i,last[0],last[1]);
    if(a[i].second!=a[i-1].second)
    {
      //printf("->%i<-\n",i);
      ll cost=0;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:18:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<r.size();i++) a[i+1]=mp(r[i],0);
          ~^~~~~~~~~
wiring.cpp:19:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<b.size();i++) a[i+1+r.size()]=mp(b[i],1);
          ~^~~~~~~~~
wiring.cpp:50:4: warning: 'ok' may be used uninitialized in this function [-Wmaybe-uninitialized]
    if(ok && a[last[a[i].second^1]-sz+1].second==(a[i].second^1))
    ^~

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