oj.uz

답안 #872824

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
872824 2023-11-13T21:56:25 Z velislavgarkov 철로 (IOI14_rail) C++14
30 / 100
 45 ms 4952 KB 
#include "rail.h"
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
const int MAXN=1e5+10;
const int MAXM=1e6+10;
struct Stantia {
    int d;
    int ind;
};
Stantia st[MAXN];
int dist[MAXN];
int um[MAXM];
set <int> lef, ri;
bool cmp(Stantia a, Stantia b) {
    return a.d<b.d;
}
void findLocation (int n, int first, int location[], int stype[]) {
    location[0]=first; stype[0]=1;
    for (int i=1;i<n;i++) {
        st[i].d=dist[i]=getDistance(0,i);
        st[i].ind=i;
    }
    sort(st+1,st+n,cmp);
    location[st[1].ind]=first+st[1].d;
    stype[st[1].ind]=2;
    int mini=0, maxi=st[1].ind;
    ri.insert(location[st[1].ind]);
    um[location[0]]=0; um[location[st[1].ind]]=st[1].ind;

    int l1, d1, d2, cur_c, cur_ind;
    for (int i=2;i<n;i++) {
        d1=getDistance(st[i].ind,st[1].ind);
        if (d1+st[1].d==st[i].d && st[i].d>2*st[1].d) {
            if (mini==0) {
                location[st[i].ind]=location[st[1].ind]-(st[i].d-st[1].d);
                stype[st[i].ind]=1;
                lef.insert(-location[st[i].ind]);
                mini=st[i].ind;
            } else {
                l1=location[mini]+(st[i].d-dist[mini]);
                cur_c=-(*lef.lower_bound(-l1));
                cur_ind=um[cur_c];
                d2=getDistance(cur_ind,st[i].ind);
                if (mini==0 || d2+dist[cur_ind]!=st[i].d) {
                    location[st[i].ind]=location[st[1].ind]-(st[i].d-st[1].d);
                    stype[st[i].ind]=1;
                    lef.insert(-location[st[i].ind]);
                    mini=st[i].ind;
                } else {
                    location[st[i].ind]=location[cur_ind]+d2;
                    stype[st[i].ind]=2;
                }
            }
        } else {
            l1=location[maxi]-(st[i].d-dist[maxi]);
            cur_c=(*ri.lower_bound(l1));
            cur_ind=um[cur_c];
            d2=getDistance(cur_ind,st[i].ind);
            if (d2+dist[cur_ind]!=st[i].d) {
                location[st[i].ind]=location[0]+st[i].d;
                stype[st[i].ind]=2;
                ri.insert(location[st[i].ind]);
            } else {
                location[st[i].ind]=location[cur_ind]-d2;
                stype[st[i].ind]=1;
            }
        }
        um[location[st[i].ind]]=st[i].ind;
    }
}

Subtask #1
8.0 / 8.0

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

Subtask #2
22.0 / 22.0

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

Subtask #3
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 45 ms 4952 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 45 ms 4712 KB Output isn't correct
2 Halted 0 ms 0 KB -