oj.uz

Submission #638617

# Submission time Handle Problem Language Result Execution time Memory
638617 2022-09-06T13:56:59 Z ggoh Rail (IOI14_rail) C++14
100 / 100
 100 ms 48684 KB 
#include "rail.h"
#include<bits/stdc++.h>
using namespace std;
#define sz(v) ((int)(v).size())
typedef pair<int,int> pii;

int dis[5005][5005],minind,ind[2000002];
void findLocation(int n, int first, int location[], int stype[])
{
    location[0]=first;
    stype[0]=1;
    if(n==1)return ;

    for(int i=1;i<n;i++)
    {
        dis[0][i]=dis[i][0]=getDistance(0,i);
        if(!minind || dis[0][minind]>dis[0][i])minind=i;
    }
    int c0,d0;
    d0=minind;
    location[d0]=location[0]+dis[0][d0];
    stype[d0]=2;
    minind=d0;
    for(int i=0;i<n;i++)
    {
        if(i==d0)continue;
        dis[d0][i]=dis[i][d0]=getDistance(d0,i);
        if(minind==d0 || dis[d0][minind]>dis[d0][i])minind=i;
    }
    c0=minind;
    location[c0]=location[d0]-dis[d0][c0];
    stype[c0]=1;
    for(int i=0;i<n;i++)
    {
        if(i==0 || i==c0 || i==d0)continue;
        dis[c0][i]=dis[0][i]-(dis[0][d0]-dis[c0][d0]);
    }
    vector<pii>ri,le;
    for(int i=0;i<n;i++)
    {
        if(i==c0 || i==d0)continue;
        if(dis[c0][i]<dis[d0][i])ri.push_back({dis[c0][i],i});
        else le.push_back({dis[d0][i],i});
    }
    sort(ri.begin(),ri.end());
    sort(le.begin(),le.end());
    //right
    int sum;
    vector<pii>D;
    memset(ind,-1,sizeof(ind));
    sum=location[d0]-location[c0];
    D.push_back({sum,d0});
    ind[sum]=sz(D)-1;
    for(auto &x:ri)
    {
        int dis=x.first;
        int i=x.second;
        int j=sz(D)-1;
        int ch=0;
        int dis2=getDistance(D[j].second,i);
        if((sum+dis-dis2)%2==0 && sum+dis-dis2>0 && ind[(sum+dis-dis2)/2]!=-1)
        {
          int k=ind[(sum+dis-dis2)/2];
          if(k>0 && D[k].first-D[k-1].first>dis2-sum+D[k].first)
          {
            ch=1;
            location[i]=location[D[k].second]-dis2+sum-D[k].first;
            stype[i]=1;
          }
        }
        if(ch==0)
        {
            location[i]=location[c0]+dis;
            stype[i]=2;
            sum=location[i]-location[c0];
            D.push_back({sum,i});
            ind[sum]=sz(D)-1;
        }
    }
    
    //left
    sum=0;
    vector<pii>C;
    memset(ind,-1,sizeof(ind));
    sum=location[d0]-location[c0];
    C.push_back({sum,c0});
    ind[sum]=sz(C)-1;
    for(auto &x:le)
    {
        int dis=x.first;
        int i=x.second;
        int j=sz(C)-1;
        int ch=0;
        int dis2=getDistance(C[j].second,i);
        if((sum+dis-dis2)%2==0 && sum+dis-dis2>0 && ind[(sum+dis-dis2)/2]!=-1)
        {
          int k=ind[(sum+dis-dis2)/2];
          if(k>0 && C[k].first-C[k-1].first>dis2-sum+C[k].first)
          {
            ch=1;
            location[i]=location[C[k].second]+dis2-sum+C[k].first;
            stype[i]=2;
          }
        }
        if(ch==0)
        {
            location[i]=location[d0]-dis;
            stype[i]=1;
            sum=location[d0]-location[i];
            C.push_back({sum,i});
            ind[sum]=sz(C)-1;
        }
    }

    return ;
}

Subtask #1
8.0 / 8.0

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

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8648 KB Output is correct
2 Correct 4 ms 8532 KB Output is correct
3 Correct 4 ms 8532 KB Output is correct
4 Correct 4 ms 8532 KB Output is correct
5 Correct 5 ms 8532 KB Output is correct
6 Correct 6 ms 8660 KB Output is correct
7 Correct 5 ms 8532 KB Output is correct
8 Correct 5 ms 8532 KB Output is correct
9 Correct 5 ms 8532 KB Output is correct
10 Correct 4 ms 8632 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 42248 KB Output is correct
2 Correct 82 ms 34548 KB Output is correct
3 Correct 94 ms 48560 KB Output is correct
4 Correct 87 ms 48632 KB Output is correct
5 Correct 93 ms 48648 KB Output is correct
6 Correct 87 ms 48588 KB Output is correct
7 Correct 86 ms 48516 KB Output is correct
8 Correct 81 ms 39160 KB Output is correct
9 Correct 84 ms 40052 KB Output is correct
10 Correct 89 ms 34284 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 42232 KB Output is correct
2 Correct 86 ms 34548 KB Output is correct
3 Correct 84 ms 48644 KB Output is correct
4 Correct 86 ms 48640 KB Output is correct
5 Correct 85 ms 48636 KB Output is correct
6 Correct 100 ms 48684 KB Output is correct
7 Correct 94 ms 48516 KB Output is correct
8 Correct 80 ms 39184 KB Output is correct
9 Correct 85 ms 40068 KB Output is correct
10 Correct 84 ms 34164 KB Output is correct
11 Correct 88 ms 42616 KB Output is correct
12 Correct 85 ms 44664 KB Output is correct
13 Correct 91 ms 48644 KB Output is correct
14 Correct 91 ms 48628 KB Output is correct
15 Correct 88 ms 48628 KB Output is correct
16 Correct 86 ms 48632 KB Output is correct
17 Correct 87 ms 48628 KB Output is correct
18 Correct 86 ms 48632 KB Output is correct
19 Correct 94 ms 48508 KB Output is correct
20 Correct 97 ms 34556 KB Output is correct