oj.uz

Submission #7754

# Submission time Handle Problem Language Result Execution time Memory
7754 2014-08-18T07:04:45 Z dohyun0324 Rail (IOI14_rail) C++
100 / 100
 168 ms 948 KB 
#include "rail.h"
#include<algorithm>
using namespace std;
int w,arr1[5010],arr2[5010];
struct data
{
    int num,dis;
    bool operator<(const data&r)const
    {
        return dis<r.dis;
    }
}left[5010];
struct data2
{
    int num,dis;
    bool operator<(const data2&r)const
    {
        return dis<r.dis;
    }
}right[5010];
void findLocation(int N, int first, int location[], int stype[])
{
    int i,j,k,dis=2147483647,p,s,dis2,pos;
    for(i=1;i<=N-1;i++)
    {
        k=getDistance(0,i);
        arr1[i]=k;
        if(dis>k) dis=k, p=i;
    }
    stype[0]=1, location[0]=first;
    stype[p]=2, location[p]=dis+location[0];
    for(i=1;i<=N-1;i++)
    {
        if(i==p) continue;
        arr2[i]=getDistance(p,i);
    }
    dis2=dis;
    for(i=1;i<=N-1;i++)
    {
        if(i==p) continue;
        if(arr1[i]-arr2[i]==dis && arr2[i]-dis<0)
        {
            location[i]=location[p]-arr2[i]; stype[i]=1;
            if(dis2>arr2[i]) dis2=arr2[i];
        }
    }
    for(i=1;i<=N-1;i++)
    {
        if(i==p) continue;
        if(arr1[i]-arr2[i]==dis && arr2[i]-dis>0)
        {
            w++; left[w].dis=arr2[i]-dis; left[w].num=i;
        }
    }
    sort(left+1,left+w+1);
    if(w>0){stype[left[1].num]=1; location[left[1].num]=first-left[1].dis;}
    s=1;
    for(i=2;i<=w;i++)
    {
        k=getDistance(left[i].num,left[s].num);
        pos=left[s].dis-k;
        for(j=1;j<i;j++)
        {
            if(stype[left[j].num]==1 && left[j].dis>pos) break;
        }
        if(left[j].dis-pos==left[i].dis-left[j].dis)
        {
            stype[left[i].num]=2; location[left[i].num]=first-pos;
        }
        else
        {
            stype[left[i].num]=1; location[left[i].num]=first-left[i].dis;
            s=i;
        }
    }
    w=0;
    for(i=1;i<=N-1;i++)
    {
        if(i==p) continue;
        if(arr1[i]-arr2[i]==dis-2*dis2)
        {
            w++; right[w].dis=arr1[i]-dis; right[w].num=i;
        }
    }
    sort(right+1,right+w+1);
    if(w>0){stype[right[1].num]=2; location[right[1].num]=first+dis+right[1].dis;}
    s=1;
    for(i=2;i<=w;i++)
    {
        k=getDistance(right[i].num,right[s].num);
        pos=right[s].dis-k;
        for(j=1;j<i;j++)
        {
            if(stype[right[j].num]==2 && right[j].dis>pos) break;
        }
        if(right[j].dis-pos==right[i].dis-right[j].dis)
        {
            stype[right[i].num]=1; location[right[i].num]=first+dis+pos;
        }
        else
        {
            stype[right[i].num]=2; location[right[i].num]=first+dis+right[i].dis;
            s=i;
        }
    }
}

Compilation message

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:31:12: warning: 'p' may be used uninitialized in this function [-Wmaybe-uninitialized]
     stype[p]=2, location[p]=dis+location[0];
            ^

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 2 ms 436 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 2 ms 492 KB Output is correct
6 Correct 3 ms 492 KB Output is correct
7 Correct 2 ms 568 KB Output is correct
8 Correct 2 ms 620 KB Output is correct
9 Correct 2 ms 620 KB Output is correct
10 Correct 2 ms 620 KB Output is correct

Subtask #2
22.0 / 22.0

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

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 832 KB Output is correct
2 Correct 127 ms 832 KB Output is correct
3 Correct 112 ms 832 KB Output is correct
4 Correct 136 ms 844 KB Output is correct
5 Correct 121 ms 844 KB Output is correct
6 Correct 126 ms 844 KB Output is correct
7 Correct 109 ms 848 KB Output is correct
8 Correct 116 ms 848 KB Output is correct
9 Correct 142 ms 848 KB Output is correct
10 Correct 113 ms 848 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 848 KB Output is correct
2 Correct 148 ms 848 KB Output is correct
3 Correct 116 ms 848 KB Output is correct
4 Correct 116 ms 848 KB Output is correct
5 Correct 116 ms 848 KB Output is correct
6 Correct 119 ms 848 KB Output is correct
7 Correct 109 ms 848 KB Output is correct
8 Correct 116 ms 848 KB Output is correct
9 Correct 114 ms 848 KB Output is correct
10 Correct 107 ms 948 KB Output is correct
11 Correct 111 ms 948 KB Output is correct
12 Correct 116 ms 948 KB Output is correct
13 Correct 168 ms 948 KB Output is correct
14 Correct 151 ms 948 KB Output is correct
15 Correct 119 ms 948 KB Output is correct
16 Correct 121 ms 948 KB Output is correct
17 Correct 151 ms 948 KB Output is correct
18 Correct 165 ms 948 KB Output is correct
19 Correct 118 ms 948 KB Output is correct
20 Correct 111 ms 948 KB Output is correct