Submission #406744

# Submission time Handle Problem Language Result Execution time Memory
406744 2021-05-18T04:04:40 Z daniel920712 Wiring (IOI17_wiring) C++14
13 / 100
156 ms 22204 KB
#include "wiring.h"
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <map>
#include <set>
#include <assert.h>
using namespace std;
long long N,M;


vector < int > x,y;
long long DP[25][200005];
long long have2[25][200005];
set < int > have;
map < int , int > cha;
int who1[100005];
int who2[100005];
int xx=0;
long long F(long long a,long long b)
{
    if(a==N&&b==M) return 0;
    if(a==N||b==M||(N>200||M>200)&&abs(who2[b]-who1[a])>10) return 1e18;
    if(have2[who2[b]-who1[a]+10][a]) return DP[who2[b]-who1[a]+10][a];
    have2[who2[b]-who1[a]+10][a]=1;
    xx++;
    assert(xx<=5000000);
    DP[who2[b]-who1[a]+10][a]=(long long) abs(y[b]-x[a])+min(F(a+1,b+1),min(F(a+1,b),F(a,b+1)));
    return DP[who2[b]-who1[a]+10][a];
}
long long min_total_length(vector< int > r, vector < int > b)
{
    long long ans=0,i,now=0;
    N=r.size();
    M=b.size();
    x=r;
    y=b;
    for(auto i:r) have.insert(i);
    for(auto i:b) have.insert(i);
    for(auto i:have) cha[i]=now++;
    for(i=0;i<N;i++) who1[i]=cha[r[i]];
    for(i=0;i<M;i++) who2[i]=cha[b[i]];
    if(b[0]>r[N-1])
    {
        if(N<=M)
        {
            for(i=0;i<min(N,M);i++) ans+=(long long) b[i]-r[i];
            for(i=N;i<M;i++) ans+=(long long) b[i]-r[N-1];
        }
        else
        {
            for(i=1;i<=M;i++) ans+=(long long) b[M-i]-r[N-i];
            for(i=0;i<N-M;i++) ans+=(long long) b[0]-r[i];
        }

        return ans;
    }
    else return F(0,0);
}

Compilation message

wiring.cpp: In function 'long long int F(long long int, long long int)':
wiring.cpp:23:34: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   23 |     if(a==N||b==M||(N>200||M>200)&&abs(who2[b]-who1[a])>10) return 1e18;
      |                    ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 588 KB 3rd lines differ - on the 1st token, expected: '25859', found: '12752'
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 113 ms 16688 KB Output is correct
4 Correct 109 ms 16668 KB Output is correct
5 Correct 132 ms 16688 KB Output is correct
6 Correct 148 ms 22128 KB Output is correct
7 Correct 149 ms 22112 KB Output is correct
8 Correct 156 ms 22156 KB Output is correct
9 Correct 149 ms 22204 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Runtime error 7 ms 760 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 620 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 588 KB 3rd lines differ - on the 1st token, expected: '25859', found: '12752'
2 Halted 0 ms 0 KB -