oj.uz

답안 #856671

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
856671 2023-10-04T09:13:27 Z abcvuitunggio 철로 (IOI14_rail) C++17
100 / 100
 51 ms 1100 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 (a<0||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 (b>=0&&!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
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 0 ms 600 KB Output is correct
8 Correct 0 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 0 ms 604 KB Output is correct

Subtask #2
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 0 ms 604 KB Output is correct
8 Correct 0 ms 604 KB Output is correct
9 Correct 0 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct

Subtask #3
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 852 KB Output is correct
2 Correct 46 ms 860 KB Output is correct
3 Correct 47 ms 860 KB Output is correct
4 Correct 45 ms 856 KB Output is correct
5 Correct 47 ms 856 KB Output is correct
6 Correct 47 ms 860 KB Output is correct
7 Correct 45 ms 844 KB Output is correct
8 Correct 45 ms 848 KB Output is correct
9 Correct 47 ms 864 KB Output is correct
10 Correct 45 ms 848 KB Output is correct

Subtask #4
44.0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 856 KB Output is correct
2 Correct 51 ms 856 KB Output is correct
3 Correct 45 ms 848 KB Output is correct
4 Correct 45 ms 856 KB Output is correct
5 Correct 44 ms 848 KB Output is correct
6 Correct 47 ms 848 KB Output is correct
7 Correct 47 ms 856 KB Output is correct
8 Correct 45 ms 860 KB Output is correct
9 Correct 45 ms 860 KB Output is correct
10 Correct 46 ms 848 KB Output is correct
11 Correct 45 ms 860 KB Output is correct
12 Correct 46 ms 852 KB Output is correct
13 Correct 48 ms 844 KB Output is correct
14 Correct 45 ms 844 KB Output is correct
15 Correct 45 ms 844 KB Output is correct
16 Correct 45 ms 848 KB Output is correct
17 Correct 45 ms 856 KB Output is correct
18 Correct 45 ms 860 KB Output is correct
19 Correct 48 ms 844 KB Output is correct
20 Correct 45 ms 1100 KB Output is correct