oj.uz

답안 #429512

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
429512 2021-06-16T04:50:59 Z TLP39 철로 (IOI14_rail) C++14
100 / 100
 102 ms 4584 KB 
#include "rail.h"
#include<bits/stdc++.h>
using namespace std;

int n;
pair<int,int> a[5003];
int cl;
int dist[2][5003];
vector<int> v[2];
int station[1000001];
int f[2];
void findLocation(int N, int start, int location[], int stype[])
{
    for(int i=0;i<1000001;i++) station[i]=-1;
    n=N;
    location[0]=start;
    stype[0]=1;
    station[start]=0;
    if(n==1) return;
    for(int i=1;i<n;i++)
    {
        a[i-1]={getDistance(0,i),i};
        dist[0][i]=a[i-1].first;
    }
    sort(a,a+n-1);
    cl=a[0].second;
    location[cl]=start+a[0].first;
    stype[cl]=2;
    station[location[cl]]=cl;
    for(int i=0;i<n-1;i++)
    {
        if(a[i].second==cl)
        {
            dist[1][cl]=0;
            continue;
        }
        dist[1][a[i].second]=getDistance(cl,a[i].second);
        if(dist[0][a[i].second]-dist[1][a[i].second]==a[0].first)
        {
            if(dist[1][a[i].second]<a[0].first)
            {
                location[a[i].second]=location[cl]-dist[1][a[i].second];
                stype[a[i].second]=1;
                station[location[a[i].second]]=a[i].second;
            }
            else
            {
                v[0].push_back(a[i].second);
            }
        }
        else
        {
            v[1].push_back(a[i].second);
        }
    }
    int turn;
    if(!v[0].empty())
    {
        int dist0;
        location[v[0][0]]=location[cl]-dist[1][v[0][0]];
        stype[v[0][0]]=1;
        station[location[v[0][0]]]=v[0][0];
        f[0]=v[0][0];
        for(int i=1;i<v[0].size();i++)
        {
            dist0=getDistance(f[0],v[0][i]);
            turn=(location[f[0]]+location[cl]+dist0-dist[1][v[0][i]])>>1;
            if(station[turn]>-1 && stype[station[turn]]==1)
            {
                location[v[0][i]]=location[f[0]]+dist0;
                stype[v[0][i]]=2;
                station[location[v[0][i]]]=v[0][i];
            }
            else
            {
                location[v[0][i]]=location[cl]-dist[1][v[0][i]];
                stype[v[0][i]]=1;
                station[location[v[0][i]]]=v[0][i];
                f[0]=v[0][i];
            }
        }
    }

    if(!v[1].empty())
    {
        int dist1;
        location[v[1][0]]=location[0]+dist[0][v[1][0]];
        stype[v[1][0]]=2;
        station[location[v[1][0]]]=v[1][0];
        f[1]=v[1][0];
        for(int i=1;i<v[1].size();i++)
        {
            dist1=getDistance(f[1],v[1][i]);
            turn=(location[f[1]]+location[0]-dist1+dist[0][v[1][i]])>>1;
            if(station[turn]>-1 && stype[station[turn]]==2)
            {
                location[v[1][i]]=location[f[1]]-dist1;
                stype[v[1][i]]=1;
                station[location[v[1][i]]]=v[1][i];
            }
            else
            {
                location[v[1][i]]=location[0]+dist[0][v[1][i]];
                stype[v[1][i]]=2;
                station[location[v[1][i]]]=v[1][i];
                f[1]=v[1][i];
            }
        }
    }
    return;
}

Compilation message

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:64:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |         for(int i=1;i<v[0].size();i++)
      |                     ~^~~~~~~~~~~~
rail.cpp:91:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |         for(int i=1;i<v[1].size();i++)
      |                     ~^~~~~~~~~~~~

Subtask #1
8.0 / 8.0

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

Subtask #2
22.0 / 22.0

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

Subtask #3
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 91 ms 4472 KB Output is correct
2 Correct 89 ms 4472 KB Output is correct
3 Correct 96 ms 4480 KB Output is correct
4 Correct 86 ms 4584 KB Output is correct
5 Correct 88 ms 4420 KB Output is correct
6 Correct 98 ms 4480 KB Output is correct
7 Correct 89 ms 4488 KB Output is correct
8 Correct 87 ms 4472 KB Output is correct
9 Correct 88 ms 4468 KB Output is correct
10 Correct 90 ms 4416 KB Output is correct

Subtask #4
44.0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Correct 102 ms 4420 KB Output is correct
2 Correct 91 ms 4476 KB Output is correct
3 Correct 86 ms 4484 KB Output is correct
4 Correct 100 ms 4420 KB Output is correct
5 Correct 87 ms 4472 KB Output is correct
6 Correct 86 ms 4472 KB Output is correct
7 Correct 87 ms 4464 KB Output is correct
8 Correct 86 ms 4480 KB Output is correct
9 Correct 91 ms 4464 KB Output is correct
10 Correct 101 ms 4548 KB Output is correct
11 Correct 94 ms 4420 KB Output is correct
12 Correct 86 ms 4484 KB Output is correct
13 Correct 86 ms 4468 KB Output is correct
14 Correct 94 ms 4480 KB Output is correct
15 Correct 86 ms 4488 KB Output is correct
16 Correct 86 ms 4420 KB Output is correct
17 Correct 96 ms 4468 KB Output is correct
18 Correct 87 ms 4480 KB Output is correct
19 Correct 86 ms 4420 KB Output is correct
20 Correct 90 ms 4472 KB Output is correct