Submission #609102

#	Time	Username	Problem	Language	Result	Execution time	Memory
609102		PiejanVDC	Wiring (IOI17_wiring)	C++17	0 / 100	1 ms	468 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
 
long long min_total_length(vector<int>r, vector<int>b) {
    const int n = (int)r.size(), m = (int)b.size();
    long long dp[45][45];
    for(int i = 0 ; i <= 40 ; i++)
        for(int j = 0 ; j <= 40 ; j++)
            dp[i][j] = 1e15;
    dp[0][0] = 0;
    int a = 0, c = 0;
    vector<pair<int,int>>v;
 
    bool ok = 1;
    int f, cnt = 0;
    for(int i = 0 ; i < n+m ; i++) {
        if(a == n) {v.push_back({1, b[c++]}); continue;}
        if(c == m) {v.push_back({0, r[a++]}); continue;}
        if(r[a] < b[c])
            v.push_back({0, r[a++]});
        else
            v.push_back({1, b[c++]});
        if(i == 0)
            f = v.back().first;
        if(ok && v.back().first == f)
            cnt++;
        else ok = 0;
    }
 
    int del = 0;
 
    int A = 0, B = 0;
    if(f) B = cnt;
    else A = cnt;
    while(A+B < n+m) {
        int len = 0;
        c = v[A+B].first;
        int ii = A+B;
        while(ii < n+m && v[ii].first == c)
            ii++, len++;
        ii = A+B-1;
        c = 1 - c;
        int prev = 0;
        while(ii >= 0 && v[ii].first == c)
            ii--, prev++;
        c = 1 - c;
        int mn = INT_MAX;
        for(int ii = A+B ; ii < A+B+len ; ii++) {
            if(c == 0) {
                int i = A+(ii - (A+B)+1);
                for(int j = B-prev+1 ; j <= B ; j++) {
                    for(int k = B-prev+1 ; k <= B ; k++)
                        dp[i-del][j-del] = min(dp[i-del][j-del], dp[i-1-del][j-del] + abs(v[ii].second - v[k+A-1].second));
                    for(int k = A+(ii - (A+B)+1) ; k <= A+len ; k++)
                        dp[i-del][j-del] = min(dp[i-del][j-del], dp[i-del][j-1-del] + abs(v[j+A-1].second - v[k+B-1].second));
                    dp[i-del][j-del] = min(dp[i-del][j-del], dp[i-1-del][j-1-del] + abs(v[ii].second - v[j+A-1].second));
                    mn = min(mn,min(i-1-del, j-1-del));
                    assert(mn >= 0);
                    //assert(i-del < 40 && j-del < 40);
                }
            } else {
               int j = B + (ii - (A+B)+1);
                for(int i = A-prev+1 ; i <= A ; i++) {
                    for(int k = A-prev+1 ; k <= A ; k++)
                        dp[i-del][j-del] = min(dp[i-del][j-del], dp[i-del][j-1-del] + abs(v[ii].second - v[k+B-1].second));
                    for(int k = B+(ii - (A+B)+1) ; k <= B+len ; k++)
                        dp[i-del][j-del] = min(dp[i-del][j-del], dp[i-1-del][j-del] + abs(v[i+B-1].second - v[k+A-1].second));
                    dp[i-del][j-del] = min(dp[i-del][j-del], dp[i-1-del][j-1-del] + abs(v[ii].second - v[i+B-1].second));
                    mn = min(mn,min(j-1-del, i-1-del));
                    assert(mn >= 0);   
                    //assert(i-del < 40 && j-del < 40);
                }
            }
        }
        if(c)
            B += len;
        else
            A += len;
        int d = mn-1;
        del += d;
        for(int i = 0 ; i <= 40 ; i++)
            for(int j = 0 ; j <= 400 ; j++)
                dp[i][j] = (i+d <= 40 && j+d <= 40 ? dp[i+d][j+d] : 1e15);
    }
 
    return dp[n-del][m-del];
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:84:26: warning: iteration 45 invokes undefined behavior [-Waggressive-loop-optimizations]
   84 |                 dp[i][j] = (i+d <= 40 && j+d <= 40 ? dp[i+d][j+d] : 1e15);
      |                 ~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
wiring.cpp:83:31: note: within this loop
   83 |             for(int j = 0 ; j <= 400 ; j++)
      |                             ~~^~~~~~
wiring.cpp:34:5: warning: 'f' may be used uninitialized in this function [-Wmaybe-uninitialized]
   34 |     if(f) B = cnt;
      |     ^~

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