oj.uz

Submission #7439

# Submission time Handle Problem Language Result Execution time Memory
7439 2014-08-05T08:49:22 Z gs13068 Rail (IOI14_rail) C++
30 / 100
 156 ms 768 KB 
#include "rail.h"
#include <algorithm>

std::pair<int,int> sta[5000];

void findLocation(int n,int fir,int loc[],int type[])
{
  int l,r;
  int ld,rd;
  int i,j,k;
  loc[0]=fir;
  type[0]=1;
  if(n>1)
  {
    for(i=1;i<n;i++)
    {
      sta[i].first=getDistance(0,i);
      sta[i].second=i;
    }
    std::sort(sta+1,sta+n);
    loc[sta[1].second]=fir+sta[1].first;
    type[sta[1].second]=2;
    l=0;
    r=sta[1].second;
    for(i=2;i<n;i++)
    {
      ld=getDistance(l,sta[i].second);
      rd=getDistance(r,sta[i].second);
      k=-1;
      for(j=0;j<i;j++)if(type[sta[j].second]==2&&loc[sta[j].second]>loc[0]&&loc[sta[j].second]>loc[r]-rd&&(k<0||loc[sta[j].second]<loc[sta[k].second]))k=j;
      if(k<0||loc[sta[k].second]-loc[0]+loc[sta[k].second]-(loc[r]-rd)!=sta[i].first)
      {
        loc[sta[i].second]=loc[l]+ld;
        type[sta[i].second]=2;
      }
      else
      {
        k=-1;
        for(j=0;j<i;j++)if(type[sta[j].second]==2&&loc[sta[j].second]>loc[l]&&loc[sta[j].second]>loc[r]-rd&&(k<0||loc[sta[j].second]<loc[sta[k].second]))k=j;
        if(k<0||loc[sta[k].second]-loc[l]+loc[sta[k].second]-(loc[r]-rd)!=ld)
        {
          loc[sta[i].second]=loc[l]+ld;
          type[sta[i].second]=2;
        }
        else
        {
          loc[sta[i].second]=loc[r]-rd;
          type[sta[i].second]=1;
        }
      }
      if(type[sta[i].second]==1&&loc[sta[i].second]<loc[l])l=sta[i].second;
      if(type[sta[i].second]==2&&loc[sta[i].second]>loc[r])r=sta[i].second;
    }
  }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 2 ms 392 KB Output is correct
4 Correct 2 ms 448 KB Output is correct
5 Correct 2 ms 472 KB Output is correct
6 Correct 2 ms 472 KB Output is correct
7 Correct 2 ms 508 KB Output is correct
8 Correct 2 ms 552 KB Output is correct
9 Correct 2 ms 572 KB Output is correct
10 Correct 2 ms 572 KB Output is correct

Subtask #2
22.0 / 22.0

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

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 152 ms 688 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Incorrect 156 ms 768 KB Output isn't correct
2 Halted 0 ms 0 KB -