# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
289950 |
2020-09-03T09:02:27 Z |
tinjyu |
Rail (IOI14_rail) |
C++14 |
|
91 ms |
7432 KB |
#include "rail.h"
#include <iostream>
#include <algorithm>
using namespace std;
long long int tag[10000005],t[100005],n,map[5005][3],l[1000005],r[1000005],lcnt,rcnt;
bool cmp1(int a,int b)
{
return map[a][1]<map[b][1];
}
bool cmp2(int a,int b)
{
return map[a][0]<map[b][0];
}
void findLocation(int N, int first, int location[], int stype[])
{
n=N;
long long int mi=9999999999,ri=0;
for(int i=1;i<n;i++)
{
map[i][0]=getDistance(0,i);
if(map[i][0]<mi)
{
mi=map[i][0];
ri=i;
}
}
location[ri]=first+mi;
location[0]=first;
stype[0]=1;
stype[ri]=2;
for(int i=1;i<n;i++)
{
map[i][1]=getDistance(ri,i);
}
//cout<<ri<<endl;
for(int i=1;i<n;i++)
{
if(ri==i || stype[i]!=0)continue;
if(map[ri][0]+map[i][1]==map[i][0])
{
if(map[i][1]<=map[ri][0])
{
location[i]=location[ri]-map[i][1];
stype[i]=1;
continue;
}
lcnt++;
l[lcnt]=i;
}
else
{
rcnt++;
r[rcnt]=i;
}
}
sort(l+1,l+lcnt+1,cmp1);
sort(r+1,r+rcnt+1,cmp2);
//for(int i=1;i<=lcnt;i++)cout<<l[i]<<" ";
//cout<<endl;
//for(int i=1;i<=rcnt;i++)cout<<r[i]<<" ";
//cout<<endl;
int p=0;
for(int i=1;i<=lcnt;i++)
{
if(p==0)
{
p++;
t[p]=l[i];
location[l[i]]=location[ri]-map[l[i]][1];
stype[l[i]]=1;
tag[location[l[i]]]=1;
}
else
{
long long int tmp=getDistance(t[p],l[i]);
long long int datla=(map[t[p]][1]+tmp-map[l[i]][1])/2;
if(tag[location[t[p]]+datla]==1 && location[t[p]]+datla<location[0])
{
location[l[i]]=location[t[p]]+tmp;
stype[l[i]]=2;
tag[location[l[i]]]=2;
}
else
{
p++;
t[p]=l[i];
location[l[i]]=location[ri]-map[l[i]][1];
stype[l[i]]=1;
tag[location[l[i]]]=1;
}
}
}
p=0;
for(int i=1;i<=rcnt;i++)
{
if(p==0)
{
p++;
t[p]=r[i];
location[r[i]]=location[0]+map[r[i]][0];
stype[r[i]]=2;
tag[location[r[i]]]=2;
}
else
{
long long int tmp=getDistance(t[p],r[i]);
long long int datla=(map[t[p]][0]+tmp-map[r[i]][0])/2;
if(tag[location[t[p]]-datla]==2 && location[t[p]]-datla>ri)
{
location[r[i]]=location[t[p]]-tmp;
stype[r[i]]=1;
tag[location[l[i]]]=1;
}
else
{
p++;
t[p]=r[i];
location[r[i]]=location[0]+map[r[i]][0];
stype[r[i]]=2;
tag[location[r[i]]]=2;
}
}
}
//for(int i=0;i<n;i++)cout<<location[i]<<" ";
//cout<<endl;
//for(int i=0;i<n;i++)cout<<stype[i]<<" ";
//cout<<endl;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
384 KB |
Output is correct |
10 |
Correct |
1 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
384 KB |
Output is correct |
10 |
Correct |
1 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
86 ms |
7160 KB |
Output is correct |
2 |
Correct |
87 ms |
7032 KB |
Output is correct |
3 |
Correct |
88 ms |
7288 KB |
Output is correct |
4 |
Correct |
88 ms |
7032 KB |
Output is correct |
5 |
Correct |
85 ms |
6520 KB |
Output is correct |
6 |
Correct |
86 ms |
6264 KB |
Output is correct |
7 |
Correct |
88 ms |
6520 KB |
Output is correct |
8 |
Correct |
91 ms |
7032 KB |
Output is correct |
9 |
Correct |
90 ms |
7032 KB |
Output is correct |
10 |
Correct |
86 ms |
6776 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
86 ms |
7160 KB |
Output is correct |
2 |
Correct |
87 ms |
7032 KB |
Output is correct |
3 |
Correct |
86 ms |
7176 KB |
Output is correct |
4 |
Correct |
87 ms |
7052 KB |
Output is correct |
5 |
Correct |
85 ms |
6528 KB |
Output is correct |
6 |
Correct |
89 ms |
6264 KB |
Output is correct |
7 |
Correct |
89 ms |
6648 KB |
Output is correct |
8 |
Correct |
87 ms |
7032 KB |
Output is correct |
9 |
Correct |
87 ms |
6904 KB |
Output is correct |
10 |
Correct |
87 ms |
6776 KB |
Output is correct |
11 |
Correct |
86 ms |
6392 KB |
Output is correct |
12 |
Correct |
87 ms |
6648 KB |
Output is correct |
13 |
Correct |
88 ms |
7160 KB |
Output is correct |
14 |
Correct |
89 ms |
7416 KB |
Output is correct |
15 |
Correct |
88 ms |
6912 KB |
Output is correct |
16 |
Correct |
88 ms |
7160 KB |
Output is correct |
17 |
Correct |
86 ms |
6264 KB |
Output is correct |
18 |
Correct |
87 ms |
7432 KB |
Output is correct |
19 |
Correct |
88 ms |
6776 KB |
Output is correct |
20 |
Correct |
86 ms |
6648 KB |
Output is correct |