oj.uz

Submission #889512

# Submission time Handle Problem Language Result Execution time Memory
889512 2023-12-19T20:59:45 Z JakobZorz Rail (IOI14_rail) C++17
100 / 100
 67 ms 980 KB 
#include"rail.h"
#include<iostream>
#include<vector>
#include<algorithm>
typedef long long ll;
using namespace std;

void findLocation(int n,int first,int location[],int stype[]){
    int calls=0;
    vector<pair<int,int>>dist0;
    vector<int>dist_from_0(n);
    for(int i=1;i<n;i++){
        dist_from_0[i]=getDistance(0,i);
        calls++;
        dist0.emplace_back(dist_from_0[i],i);
    }
    sort(dist0.begin(),dist0.end());
    
    int left=0,right=0;
    stype[0]=1;
    location[0]=0;
    
    //for(auto i:dist0)
        //cout<<i.first<<" "<<i.second<<"\n";
    
    for(auto[dist,i]:dist0){
        if(right==0){
            right=i;
            location[i]=dist;
            stype[i]=2;
            continue;
        }
        
        int dist1=getDistance(dist0[0].second,i);
        calls++;
        if(dist1+dist0[0].first==dist){ // i is on the left side
            dist-=2*dist0[0].first;
            if(dist<0){
                location[i]=-dist;
                stype[i]=1;
                continue;
            }
            
            if(left==0){
                location[i]=-dist;
                stype[i]=1;
                left=i;
                continue;
            }
            
            int dist2=getDistance(left,i);
            int mid=(location[left]+dist2-dist)/2;
            
            bool is_left=false;
            for(int i=0;i<n;i++){
                if(location[i]==mid&&stype[i]==1){
                    is_left=true;
                }
            }
            
            if(dist2>location[left]&&is_left){
                location[i]=location[left]+dist2;
                stype[i]=2;
            }else{
                left=i;
                location[i]=-dist;
                stype[i]=1;
            }
            
        }else{ // i is on the right side
            int dist2=getDistance(right,i);
            int mid=(location[right]-dist2+dist)/2;
            
            bool is_left=false;
            for(int i=0;i<n;i++){
                if(location[i]==mid&&stype[i]==2){
                    is_left=true;
                }
            }
            
            if(dist2<location[right]&&is_left){
                location[i]=location[right]-dist2;
                stype[i]=1;
            }else{
                right=i;
                location[i]=dist;
                stype[i]=2;
            }
        }
    }
    
    for(int i=0;i<n;i++){
        location[i]+=first;
        //if(n<20) cout<<stype[i]<<" "<<location[i]<<"\n";
    }
    
    //cout<<"limit: "<<3*(n-1)<<" calls: "<<calls<<"\n";
}

Subtask #1
8.0 / 8.0

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

Subtask #2
22.0 / 22.0

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

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 604 KB Output is correct
2 Correct 62 ms 600 KB Output is correct
3 Correct 59 ms 604 KB Output is correct
4 Correct 64 ms 980 KB Output is correct
5 Correct 61 ms 600 KB Output is correct
6 Correct 60 ms 600 KB Output is correct
7 Correct 60 ms 648 KB Output is correct
8 Correct 60 ms 600 KB Output is correct
9 Correct 65 ms 760 KB Output is correct
10 Correct 60 ms 604 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 604 KB Output is correct
2 Correct 59 ms 648 KB Output is correct
3 Correct 59 ms 644 KB Output is correct
4 Correct 67 ms 980 KB Output is correct
5 Correct 59 ms 600 KB Output is correct
6 Correct 60 ms 604 KB Output is correct
7 Correct 60 ms 604 KB Output is correct
8 Correct 60 ms 636 KB Output is correct
9 Correct 60 ms 604 KB Output is correct
10 Correct 60 ms 648 KB Output is correct
11 Correct 59 ms 600 KB Output is correct
12 Correct 60 ms 648 KB Output is correct
13 Correct 61 ms 632 KB Output is correct
14 Correct 61 ms 848 KB Output is correct
15 Correct 60 ms 604 KB Output is correct
16 Correct 60 ms 604 KB Output is correct
17 Correct 62 ms 604 KB Output is correct
18 Correct 60 ms 632 KB Output is correct
19 Correct 63 ms 976 KB Output is correct
20 Correct 61 ms 600 KB Output is correct