oj.uz

Submission #856670

# Submission time Handle Problem Language Result Execution time Memory
856670 2023-10-04T09:12:08 Z abcvuitunggio Rail (IOI14_rail) C++17
70 / 100
 50 ms 1092 KB 
#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
void findLocation(int N, int first, int location[], int stype[]){
    bitset <1000001> bs;
    int d[N],mn=1e9,l=0,r=-1;
    location[0]=first;
    stype[0]=1;
    vector <pair <int, int>> ve;
    set <int> sl,sr;
    for (int i=1;i<N;i++){
        d[i]=getDistance(0,i);
        if (d[i]<mn){
            mn=d[i];
            r=i;
        }
    }
    location[r]=first+mn;
    bs[first]=1;
    bs[first+mn]=1;
    stype[r]=2;
    for (int i=1;i<N;i++)
        if (i!=r)
            ve.emplace_back(d[i],i);
    sort(ve.begin(),ve.end());
    sl.insert(-first);
    sr.insert(first+mn);
    for (auto [dist,i]:ve){
        int x=getDistance(l,i),y=getDistance(r,i);
        int a=location[l]+x,b=location[r]-y;
        bool ch=0;
        if (bs[a])
            ch=1;
        if (a>first&&a<first+mn)
            ch=1;
        else if (a<first)
            ch|=(location[r]+a+*sl.lower_bound(-a)*2!=y);
        else if (!bs[b]){
            if (b>first)
                ch=(*sr.lower_bound(b)*2-location[l]-b==x);
            else
                ch=(y-dist==location[r]-first-mn*2);
        }
        if (ch){
            location[i]=b;
            bs[b]=1;
            stype[i]=1;
            if (location[i]<location[l]){
                l=i;
                sl.insert(-b);
            }
            continue;
        }
        location[i]=a;
        bs[a]=1;
        stype[i]=2;
        if (location[i]>location[r]){
            r=i;
            sr.insert(a);
        }
    }
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 860 KB Execution killed with signal 7
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 604 KB Output is correct
2 Runtime error 1 ms 856 KB Execution killed with signal 7
3 Halted 0 ms 0 KB -

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 852 KB Output is correct
2 Correct 45 ms 1092 KB Output is correct
3 Correct 46 ms 856 KB Output is correct
4 Correct 45 ms 844 KB Output is correct
5 Correct 45 ms 844 KB Output is correct
6 Correct 45 ms 848 KB Output is correct
7 Correct 46 ms 848 KB Output is correct
8 Correct 45 ms 848 KB Output is correct
9 Correct 46 ms 856 KB Output is correct
10 Correct 45 ms 852 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 844 KB Output is correct
2 Correct 45 ms 860 KB Output is correct
3 Correct 48 ms 848 KB Output is correct
4 Correct 46 ms 848 KB Output is correct
5 Correct 44 ms 844 KB Output is correct
6 Correct 46 ms 848 KB Output is correct
7 Correct 49 ms 852 KB Output is correct
8 Correct 45 ms 848 KB Output is correct
9 Correct 46 ms 860 KB Output is correct
10 Correct 47 ms 840 KB Output is correct
11 Correct 45 ms 860 KB Output is correct
12 Correct 45 ms 900 KB Output is correct
13 Correct 46 ms 848 KB Output is correct
14 Correct 45 ms 888 KB Output is correct
15 Correct 45 ms 848 KB Output is correct
16 Correct 46 ms 888 KB Output is correct
17 Correct 48 ms 888 KB Output is correct
18 Correct 47 ms 852 KB Output is correct
19 Correct 49 ms 900 KB Output is correct
20 Correct 49 ms 852 KB Output is correct