oj.uz

Submission #581523

# Submission time Handle Problem Language Result Execution time Memory
581523 2022-06-22T17:26:34 Z wdjpng Rail (IOI14_rail) C++17
30 / 100
 154 ms 196424 KB 
#include "rail.h"
#include <bits/stdc++.h>

#define int long long
#define rep(i,n) for(int i = 0; i < n; i++)
#define all(a) a.begin(), a.end()
using namespace std;

void findLocation(signed n, signed first, signed lo[], signed sty[])
{
    vector<vector<int>>dist(n, vector<int>(n));
    vector<int>location(n);
    vector<int>stype(n);

    vector<int>d0(n);
    int minn=1e12,mini=-1;
    for(int i = 1; i < n; i++) {
        int d = d0[i] = getDistance(0,i);
        if(d<minn) {minn=d; mini=i;}
    }

    vector<int>dmini(n);
    dmini[0]=d0[mini];
    rep(i,n) if(i!=0&&i!=mini) dmini[i]=getDistance(i,mini);
    int l=-1, maxl=0, r=-1, maxr=0;
    rep(i,n)
    {
        if(d0[i]<dmini[i]&&maxr<d0[i]) 
        {
            maxr= d0[i];
            r=i;
        } 
        if(dmini[i]<d0[i]&&maxl<dmini[i])
        {
            maxl=dmini[i];
            l=i;
        }
    }

    if(l==-1) l=0;
    if(r==-1) r=mini;

    stype[0]=1;
    stype[mini]=2;
    location[0]=first;
    location[mini]=first+d0[mini];
    stype[r]=2;
    stype[l]=1;
    location[l]=location[mini]-dmini[l];
    location[r]=location[0]+d0[r];

    rep(i,n) {
        if(i==0||i==mini||i==r||i==l) continue;
        if(dmini[i]<d0[i])
        {
            int dist_to_l = getDistance(i,l);
            if(dist_to_l+dmini[l]==dmini[i])
            {
                stype[i]=2;
                location[i]=location[l]+dist_to_l;
            } else {
                stype[i]=1;
                location[i]=location[mini]-dmini[i];
            }
        } else 
        {
            int dist_to_r = getDistance(i,r);
            if(dist_to_r+d0[r]==d0[i])
            {
                stype[i]=1;
                location[i]=location[r]-dist_to_r;
            } else {
                stype[i]=2;
                location[i]=location[0]+d0[i];
            }
        }
    }
    rep(i,n) sty[i]=stype[i];
    rep(i,n) lo[i]=location[i];
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 148 ms 196420 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Incorrect 154 ms 196424 KB Output isn't correct
2 Halted 0 ms 0 KB -