oj.uz

Submission #794384

# Submission time Handle Problem Language Result Execution time Memory
794384 2023-07-26T13:48:08 Z ma_moutahid Rail (IOI14_rail) C++17
30 / 100
 51 ms 972 KB 
#include <bits/stdc++.h>
#include "rail.h"
using ll =long long;
ll LINF=1000000000000000000;
int INF=1000000000;
#define pi pair<int,int>
#define pl pair<ll,ll>
#define endl '\n'
#define vi vector<int>
#define vii vector<vector<int>>
#define vl vector<ll>
#define vll vector<vector<ll>>

using namespace std;

void findLocation(int n, int first, int location[], int stype[]){
    int second;
    location[0]=first;
    multimap<int,int>df;
    vi distf(n);
    vi dists(n);
    for(int i =1;i<n;i++){
        int dist=getDistance(i,0);
        df.insert(make_pair(dist,i));
        distf[i]=dist;
    }
    second=df.begin()->second;

    for(int i=1;i<n;i++){
        if(i==second)continue;
        int dist=getDistance(i,second);
        dists[i]=dist;
    }
    location[second]=first+distf[second];
    stype[0]=1;
    stype[second]=2;
    for(int i=0;i<n;i++){
        if(i==0 || i==second)continue;
        if(dists[i]<distf[second] && distf[i]==dists[i]+ distf[second] ){
            stype[i]=1;
            location[i]=location[second]-dists[i];
        }
    }
    multimap<int,int>left;
    multimap<int,int>right;
    dists[0]=distf[second];
    for(int i=0;i<n;i++){
        if(stype[i] )continue;
        if(distf[i]==distf[second]+dists[i])left.insert(make_pair(dists[i],i));
        else right.insert(make_pair(distf[i],i));
    }
    int last=second;
    for(auto itr=right.begin();itr!=right.end();itr++){
        int dist= getDistance(itr->second,last);
        if(distf[itr->second]==distf[last]+dist){
            location[itr->second]=location[last]-dist;
            stype[itr->second]=1;
        }
        else{
            location[itr->second]=first+distf[itr->second];
            stype[itr->second]=2;
            last=itr->second;
        }
    }
    last=0;
    for(auto itr=left.begin();itr!=left.end();itr++){
        int dist= getDistance(itr->second,last);
        if(dists[itr->second]==dists[last]+dist){
            location[itr->second]=location[last]+dist;
            stype[itr->second]=2;
        }
        else{
            location[itr->second]= location[second]-dists[itr->second];
            stype[itr->second]=1;
            last=itr->second;
        }
    }


}

Subtask #1
8.0 / 8.0

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

Subtask #2
22.0 / 22.0

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

Subtask #3
0 / 26.0

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

Subtask #4
0 / 44.0

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