Submission #1135629

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135629		nightfal	Stations (IOI20_stations)	C++17	Compilation error	0 ms	0 KiB

stations

// #include "wiring.h"
#include <cassert>
#include <cstdio>
#include <vector>
#include <climits>
#include <stdlib.h>
#include <algorithm>

using namespace std;
 
bool isSubtask1(const vector<int>& r, const vector<int>& b) {return r.size()<=200 && b.size()<=200;}
bool isSubtask2(const vector<int>& r, const vector<int>& b) {return r[r.size()-1]<b[0];}
bool isSubtask3(const vector<int>& r, const vector<int>& b) {
    int n=r.size(), m=b.size();
    vector<int> a(n+m);
   
    for(int i=0, j=0; i<n || j<m;)
        i==n? a[i+j++]=1: j==m? a[j+i++]=0: r[i]<b[j]? a[j+i++]=0:a[i+j++] = 1;

    int cnt = 1;
    for(int k=1; k<n+m; k++) {
        cnt = a[k]==a[k-1]? cnt+1:0;
        if (cnt > 6) return false;
    }
  return true;
}
bool isSubtask4(const vector<int>& r, const vector<int>& b) {
    return min(r[0],b[0])==1 && max(r[r.size()-1],b[b.size()-1])==r.size()+b.size();
}
 
long long subtask1(const vector<int>&, const vector<int>&);
long long subtask2(const vector<int>&, const vector<int>&);
long long subtask2DP(const vector<pair<int,int>>&, vector<long long>&, int, int);
long long subtask3(vector<int>, vector<int>);
long long subtask4(vector<int>, vector<int>);
long long fulltask(vector<int>, vector<int>);
long long min_total_length(vector<int>, vector<int> );

 
long long min_total_length(vector<int> r, vector<int> b) {
//    return fulltask(r,b);
    // if (isSubtask4(r,b)) return subtask4(r,b);
    if (isSubtask3(r,b)) return subtask3(r,b);
  	else if (isSubtask2(r,b)) return subtask2(r,b);    
  	 else if (isSubtask1(r,b)) return subtask1(r,b);
    return 0;
}

long long fulltask(vector<int> r, vector<int> b) {
    int n = r.size(), m = b.size();
    vector<pair<int,int>> a(n+m);
    
    for(int i=0, j=0; i<n || j<m;)
        i==n? a[i+j++]=make_pair(j,1): j==m? a[j+i++]=make_pair(i,0): r[i]<b[j]? a[j+i++]=make_pair(i,0): a[i+j++]=make_pair(j,1);

    vector<long long> dp(n+m,LLONG_MAX);

    long long sumL=0, cntL=0, sumR=0, cntR=0, gap=0;
    int prev=-1, curr=0, optIdx=0;

    for(int i=1; i<n+m; i++) {
        vector<int> *left, *right;
        if (a[i].second != a[i-1].second) {
            prev=curr; curr=i; sumR=cntR=0; sumL=0; optIdx=curr-1;
            if (a[prev].second==0) {left=&r; right=&b;}
            else {left=&b; right=&r;}
            gap = (*right)[a[curr].first]-(*left)[a[curr-1].first];
        }

        if (prev==-1) continue;

        sumR += (*right)[a[i].first]-(*right)[a[curr].first];
        cntR++;

        for(int j=optIdx; j>=prev; j--) {
            cntL=curr-j; 
            sumL += (*left)[a[curr-1].first]-(*left)[a[j].first];
            if(prev==0 && j!=0) continue;
            long long temp = sumL + sumR + max(cntL,cntR)*gap;
            if (prev!=0) temp += min(dp[j-1],dp[j]);
            if (dp[i]>temp) {dp[i]=temp; optIdx=j;}
                else break;            
        }
        for(int k=max(optIdx-1,prev); k<=optIdx; k++)
            sumL -= (*left)[a[curr-1].first]-(*left)[a[k].first];
    }
    return dp[n+m-1];
}

long long subtask4(vector<int> r, vector<int> b) {
    int n = r.size(), m = b.size();
    vector<int> a(n+m);
    
    for(int i=0, j=0; i<n || j<m;)
        i==n? a[i+j++]=1: j==m? a[j+i++]=0: r[i]<b[j]? a[j+i++]=0: a[i+j++]=1;

    long long dp1=LLONG_MAX, dp2=LLONG_MAX;
    long long cntL=0, cntR=1;
    int prev=-1, curr=0; 

    for(int i=1; i<n+m; i++) {
        if (a[i]!=a[i-1]) {prev=curr; curr=i; cntL=cntR, cntR=0;}
        cntR++;

        long long cntL1 = cntL/2, cntL2 = (cntL+1)/2;                
        long long cntR1 = cntR/2, cntR2 = (cntR+1)/2;

        long long sumL = cntL*(cntL-1)/2, sumR = cntR*(cntR-1)/2; 
        long long sumL1 = cntL1*(cntL1-1)/2, sumL2 = cntL2*(cntL2-1)/2; 
        long long sumR1 = cntR1*(cntR1-1)/2, sumR2 = cntR2*(cntR2-1)/2;

        if(i==n+m-1) {
            if(prev==0) // can be omitted because it is the same as subtask2
                return sumL + max(cntL,cntR) + sumR;
            else 
                return min(dp1 + sumL2 + max(cntL2,cntR), dp2 + sumL1 + max(cntL1,cntR)) + sumR;
        }
        else if (a[i]!= a[i+1]) { 
            if (prev==0) {
                dp1 = sumL + max(cntL,cntR1) + sumR1; 
                dp2 = sumL + max(cntL,cntR2) + sumR2;            
            }
            else {
                long long new_dp1 = min(dp1 + sumL2 + max(cntL2,cntR1), dp2 + sumL1 + max(cntL1,cntR1)) + sumR1;
                long long new_dp2 = min(dp1 + sumL2 + max(cntL2,cntR2), dp2 + sumL1 + max(cntL1,cntR2)) + sumR2;
                dp1 = new_dp1; dp2 = new_dp2;
            }
        }
    }
}

long long subtask3(vector<int>& r, vector<int>& b) {
    int n = r.size(), m = b.size();
    vector<pair<int,int>> a(n+m);
    
    for(int i=0, j=0; i<n || j<m;) // ++ is not permitted in make_pair 
        i==n? a[i+j++]=make_pair(j,1): j==m? a[j+i++]=make_pair(i,0): r[i]<b[j]? a[j+i++]=make_pair(i,0): a[i+j++]=make_pair(j,1);

    vector<long long> dp(n+m,LLONG_MAX);
    int e1=0, e2=n+m-1;
    for(int i = 0;  i<n+m; i++) if (a[i].second != a[i+1].second) {e1 = i; break;}
    for(int i=e1+1; i<n+m-1; i++) if (a[i].second != a[i+1].second) {e2 = i; break;}
    subtask2DP(a,dp,e1,e2);

    long long sumL=0, cntL=0, sumR=0, cntR=0, gap=0;
    int prev=e1+1, curr=e2;

    for(int i=e2+1; i<n+m; i++) {
        vector<int> *left, *right;
        if (a[i].second != a[i-1].second) {
            prev=curr; curr=i; sumR=cntR=0;
            if(a[prev].second==0) {left=&r; right=&b;}
            else {left=&b; right=&r;}
            gap= (*right)[a[curr].first]-(*left)[a[curr-1].first];
        }
        if (prev==-1) continue;

        sumR += (*right)[a[i].first]-(*right)[a[curr].first];
        cntR++;

        for(int j=curr-1; j>=prev; j--) {
            cntL++;
            sumL += (*left)[a[curr-1].first]-(*left)[a[j].first];
            if (prev==0 && j!=0) continue;
            long long temp = sumL + sumR + max(cntL,cntR)*gap;
            if (prev!=0) temp += min(dp[j-1],dp[j]);
            dp[i] = min(dp[i], temp);
        }
        sumL=cntL=0;
    }
    return dp[n+m-1];
}
void subtask2DP(const vector<pair<int,int>> &a, vector<long long>& dp, int e1, int e2) {
    long long sum1=0, sum2=0, n = e1+1, m=e2-e1;
    for(int i=0; i<=e1; i++) sum1 += a[e1] - a[i];
    for(int i=e1+1; i<=e2; i++) { 
        sum2 += a[i] - a[e1+1];
        dp[i] = sum1+sum2+max(n,i-e1)*(a[e1+1]-a[e1]);
    }
    return;
}
long long subtask2(const vector<int>& r, const vector<int>& b) {
  long long sum1=0, sum2=0, n=r.size(), m=b.size();
  for(int i=0; i<n; i++) sum1 += r[n-1] - r[i];
  for(int i=0; i<m; i++) sum2 += b[i] - b[0];
  return sum1+sum2+max(n,m)*(b[0]-r[n-1]);
}
long long subtask1(const vector<int>& r, const vector<int>& b) {
	int n = r.size(), m = b.size();
    long long dp[n][m];
  	dp[0][0] = abs(r[0]-b[0]);
  	for(int i=1; i<n; i++) dp[i][0] = dp[i-1][0] + abs(r[i]-b[0]);
    for(int j=1; j<m; j++) dp[0][j] = dp[0][j-1] + abs(r[0]-b[j]);
  	for(int i=1; i<n; i++)  	
      for(int j=1; j<m; j++)
        dp[i][j] = min(min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1]) + abs(r[i]-b[j]);

	return dp[n-1][m-1];
}

Compilation message (stderr)

stations.cpp:173:6: error: ambiguating new declaration of 'void subtask2DP(const std::vector<std::pair<int, int> >&, std::vector<long long int>&, int, int)'
  173 | void subtask2DP(const vector<pair<int,int>> &a, vector<long long>& dp, int e1, int e2) {
      |      ^~~~~~~~~~
stations.cpp:33:11: note: old declaration 'long long int subtask2DP(const std::vector<std::pair<int, int> >&, std::vector<long long int>&, int, int)'
   33 | long long subtask2DP(const vector<pair<int,int>>&, vector<long long>&, int, int);
      |           ^~~~~~~~~~
stations.cpp: In function 'void subtask2DP(const std::vector<std::pair<int, int> >&, std::vector<long long int>&, int, int)':
stations.cpp:175:44: error: no match for 'operator-' (operand types are 'const value_type' {aka 'const std::pair<int, int>'} and 'const value_type' {aka 'const std::pair<int, int>'})
  175 |     for(int i=0; i<=e1; i++) sum1 += a[e1] - a[i];
In file included from /usr/include/c++/11/bits/stl_algobase.h:67,
                 from /usr/include/c++/11/vector:60,
                 from stations.cpp:4:
/usr/include/c++/11/bits/stl_iterator.h:577:5: note: candidate: 'template<class _IteratorL, class _IteratorR> constexpr decltype ((__y.base() - __x.base())) std::operator-(const std::reverse_iterator<_Iterator>&, const std::reverse_iterator<_IteratorR>&)'
  577 |     operator-(const reverse_iterator<_IteratorL>& __x,
      |     ^~~~~~~~
/usr/include/c++/11/bits/stl_iterator.h:577:5: note:   template argument deduction/substitution failed:
stations.cpp:175:49: note:   'const value_type' {aka 'const std::pair<int, int>'} is not derived from 'const std::reverse_iterator<_Iterator>'
  175 |     for(int i=0; i<=e1; i++) sum1 += a[e1] - a[i];
      |                                                 ^
In file included from /usr/include/c++/11/bits/stl_algobase.h:67,
                 from /usr/include/c++/11/vector:60,
                 from stations.cpp:4:
/usr/include/c++/11/bits/stl_iterator.h:1693:5: note: candidate: 'template<class _IteratorL, class _IteratorR> constexpr decltype ((__x.base() - __y.base())) std::operator-(const std::move_iterator<_IteratorL>&, const std::move_iterator<_IteratorR>&)'
 1693 |     operator-(const move_iterator<_IteratorL>& __x,
      |     ^~~~~~~~
/usr/include/c++/11/bits/stl_iterator.h:1693:5: note:   template argument deduction/substitution failed:
stations.cpp:175:49: note:   'const value_type' {aka 'const std::pair<int, int>'} is not derived from 'const std::move_iterator<_IteratorL>'
  175 |     for(int i=0; i<=e1; i++) sum1 += a[e1] - a[i];
      |                                                 ^
stations.cpp:177:22: error: no match for 'operator-' (operand types are 'const value_type' {aka 'const std::pair<int, int>'} and 'const value_type' {aka 'const std::pair<int, int>'})
  177 |         sum2 += a[i] - a[e1+1];
In file included from /usr/include/c++/11/bits/stl_algobase.h:67,
                 from /usr/include/c++/11/vector:60,
                 from stations.cpp:4:
/usr/include/c++/11/bits/stl_iterator.h:577:5: note: candidate: 'template<class _IteratorL, class _IteratorR> constexpr decltype ((__y.base() - __x.base())) std::operator-(const std::reverse_iterator<_Iterator>&, const std::reverse_iterator<_IteratorR>&)'
  577 |     operator-(const reverse_iterator<_IteratorL>& __x,
      |     ^~~~~~~~
/usr/include/c++/11/bits/stl_iterator.h:577:5: note:   template argument deduction/substitution failed:
stations.cpp:177:30: note:   'const value_type' {aka 'const std::pair<int, int>'} is not derived from 'const std::reverse_iterator<_Iterator>'
  177 |         sum2 += a[i] - a[e1+1];
      |                              ^
In file included from /usr/include/c++/11/bits/stl_algobase.h:67,
                 from /usr/include/c++/11/vector:60,
                 from stations.cpp:4:
/usr/include/c++/11/bits/stl_iterator.h:1693:5: note: candidate: 'template<class _IteratorL, class _IteratorR> constexpr decltype ((__x.base() - __y.base())) std::operator-(const std::move_iterator<_IteratorL>&, const std::move_iterator<_IteratorR>&)'
 1693 |     operator-(const move_iterator<_IteratorL>& __x,
      |     ^~~~~~~~
/usr/include/c++/11/bits/stl_iterator.h:1693:5: note:   template argument deduction/substitution failed:
stations.cpp:177:30: note:   'const value_type' {aka 'const std::pair<int, int>'} is not derived from 'const std::move_iterator<_IteratorL>'
  177 |         sum2 += a[i] - a[e1+1];
      |                              ^
stations.cpp:178:30: error: no matching function for call to 'max(long long int&, int)'
  178 |         dp[i] = sum1+sum2+max(n,i-e1)*(a[e1+1]-a[e1]);
      |                           ~~~^~~~~~~~
In file included from /usr/include/c++/11/vector:60,
                 from stations.cpp:4:
/usr/include/c++/11/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  254 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/11/bits/stl_algobase.h:254:5: note:   template argument deduction/substitution failed:
stations.cpp:178:30: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
  178 |         dp[i] = sum1+sum2+max(n,i-e1)*(a[e1+1]-a[e1]);
      |                           ~~~^~~~~~~~
In file included from /usr/include/c++/11/vector:60,
                 from stations.cpp:4:
/usr/include/c++/11/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  300 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/11/bits/stl_algobase.h:300:5: note:   template argument deduction/substitution failed:
stations.cpp:178:30: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
  178 |         dp[i] = sum1+sum2+max(n,i-e1)*(a[e1+1]-a[e1]);
      |                           ~~~^~~~~~~~
In file included from /usr/include/c++/11/algorithm:62,
                 from stations.cpp:7:
/usr/include/c++/11/bits/stl_algo.h:3461:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
 3461 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/11/bits/stl_algo.h:3461:5: note:   template argument deduction/substitution failed:
stations.cpp:178:30: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
  178 |         dp[i] = sum1+sum2+max(n,i-e1)*(a[e1+1]-a[e1]);
      |                           ~~~^~~~~~~~
In file included from /usr/include/c++/11/algorithm:62,
                 from stations.cpp:7:
/usr/include/c++/11/bits/stl_algo.h:3467:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
 3467 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/11/bits/stl_algo.h:3467:5: note:   template argument deduction/substitution failed:
stations.cpp:178:30: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
  178 |         dp[i] = sum1+sum2+max(n,i-e1)*(a[e1+1]-a[e1]);
      |                           ~~~^~~~~~~~
stations.cpp:178:47: error: no match for 'operator-' (operand types are 'const value_type' {aka 'const std::pair<int, int>'} and 'const value_type' {aka 'const std::pair<int, int>'})
  178 |         dp[i] = sum1+sum2+max(n,i-e1)*(a[e1+1]-a[e1]);
In file included from /usr/include/c++/11/bits/stl_algobase.h:67,
                 from /usr/include/c++/11/vector:60,
                 from stations.cpp:4:
/usr/include/c++/11/bits/stl_iterator.h:577:5: note: candidate: 'template<class _IteratorL, class _IteratorR> constexpr decltype ((__y.base() - __x.base())) std::operator-(const std::reverse_iterator<_Iterator>&, const std::reverse_iterator<_IteratorR>&)'
  577 |     operator-(const reverse_iterator<_IteratorL>& __x,
      |     ^~~~~~~~
/usr/include/c++/11/bits/stl_iterator.h:577:5: note:   template argument deduction/substitution failed:
stations.cpp:178:52: note:   'const value_type' {aka 'const std::pair<int, int>'} is not derived from 'const std::reverse_iterator<_Iterator>'
  178 |         dp[i] = sum1+sum2+max(n,i-e1)*(a[e1+1]-a[e1]);
      |                                                    ^
In file included from /usr/include/c++/11/bits/stl_algobase.h:67,
                 from /usr/include/c++/11/vector:60,
                 from stations.cpp:4:
/usr/include/c++/11/bits/stl_iterator.h:1693:5: note: candidate: 'template<class _IteratorL, class _IteratorR> constexpr decltype ((__x.base() - __y.base())) std::operator-(const std::move_iterator<_IteratorL>&, const std::move_iterator<_IteratorR>&)'
 1693 |     operator-(const move_iterator<_IteratorL>& __x,
      |     ^~~~~~~~
/usr/include/c++/11/bits/stl_iterator.h:1693:5: note:   template argument deduction/substitution failed:
stations.cpp:178:52: note:   'const value_type' {aka 'const std::pair<int, int>'} is not derived from 'const std::move_iterator<_IteratorL>'
  178 |         dp[i] = sum1+sum2+max(n,i-e1)*(a[e1+1]-a[e1]);
      |                                                    ^
stations.cpp: In function 'long long int subtask4(std::vector<int>, std::vector<int>)':
stations.cpp:130:1: warning: control reaches end of non-void function [-Wreturn-type]
  130 | }
      | ^