| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 399762 | 2021-05-06T14:48:15 Z | Jasiekstrz | 철로 (IOI14_rail) | C++17 | 99 ms | 708 KB |
#include<bits/stdc++.h>
#include "rail.h"
#define fi first
#define se second
using namespace std;
const int NN=5e3;
const int INF=1e9+7;
vector<pair<int,int>> t;
map<int,int> by_pos;
void findLocation(int N,int first,int location[],int stype[])
{
location[0]=first;
stype[0]=1;
by_pos[first]=0;
t.reserve(N+10);
for(int i=1;i<N;i++)
t.emplace_back(getDistance(0,i),i);
sort(t.begin(),t.end());
reverse(t.begin(),t.end());
int a=0,b=0;
b=t.back().se;
stype[b]=2;
location[b]=first+t.back().fi;
by_pos[location[b]]=b;
t.pop_back();
while(!t.empty())
{
int v=t.back().se;
int x=getDistance(a,v),y=getDistance(b,v),z=t.back().fi;
t.pop_back();
int c;
int c1=location[a]+x;
int c2=location[b]-y;
int mid=(c1+c2)/2;
//cerr<<v<<": a="<<a<<" b="<<b<<" x="<<x<<" y="<<y<<" z="<<z<<" c1="<<c1<<" c2="<<c2<<" ";
if(by_pos.find(mid)!=by_pos.end())
{
if(stype[by_pos[mid]]==1)
stype[v]=2;
else
stype[v]=1;
}
else if(first<mid)
stype[v]=2;
else // first>mid
stype[v]=1;
if(stype[v]==1)
c=c2;
else
c=c1;
location[v]=c;
by_pos[c]=v;
if(c>location[b])
b=v;
else if(c<location[a])
a=v;
//cerr<<"c="<<c<<"\n";
}
return;
}
Compilation message
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 204 KB | Output is correct |
| 2 | Correct | 1 ms | 204 KB | Output is correct |
| 3 | Correct | 1 ms | 204 KB | Output is correct |
| 4 | Correct | 1 ms | 204 KB | Output is correct |
| 5 | Correct | 1 ms | 204 KB | Output is correct |
| 6 | Correct | 1 ms | 204 KB | Output is correct |
| 7 | Correct | 1 ms | 204 KB | Output is correct |
| 8 | Correct | 1 ms | 204 KB | Output is correct |
| 9 | Correct | 1 ms | 204 KB | Output is correct |
| 10 | Correct | 1 ms | 204 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 204 KB | Output is correct |
| 2 | Correct | 1 ms | 204 KB | Output is correct |
| 3 | Correct | 1 ms | 304 KB | Output is correct |
| 4 | Correct | 1 ms | 204 KB | Output is correct |
| 5 | Correct | 1 ms | 204 KB | Output is correct |
| 6 | Correct | 1 ms | 204 KB | Output is correct |
| 7 | Correct | 1 ms | 204 KB | Output is correct |
| 8 | Correct | 1 ms | 204 KB | Output is correct |
| 9 | Correct | 1 ms | 300 KB | Output is correct |
| 10 | Correct | 1 ms | 204 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 85 ms | 692 KB | Output is correct |
| 2 | Correct | 86 ms | 692 KB | Output is correct |
| 3 | Correct | 84 ms | 696 KB | Output is correct |
| 4 | Correct | 85 ms | 684 KB | Output is correct |
| 5 | Correct | 85 ms | 688 KB | Output is correct |
| 6 | Correct | 92 ms | 672 KB | Output is correct |
| 7 | Correct | 89 ms | 676 KB | Output is correct |
| 8 | Correct | 87 ms | 684 KB | Output is correct |
| 9 | Correct | 86 ms | 676 KB | Output is correct |
| 10 | Correct | 86 ms | 672 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 99 ms | 708 KB | Output is correct |
| 2 | Correct | 96 ms | 676 KB | Output is correct |
| 3 | Correct | 84 ms | 708 KB | Output is correct |
| 4 | Correct | 86 ms | 680 KB | Output is correct |
| 5 | Correct | 93 ms | 708 KB | Output is correct |
| 6 | Correct | 85 ms | 672 KB | Output is correct |
| 7 | Correct | 86 ms | 696 KB | Output is correct |
| 8 | Correct | 94 ms | 688 KB | Output is correct |
| 9 | Correct | 85 ms | 684 KB | Output is correct |
| 10 | Correct | 89 ms | 684 KB | Output is correct |
| 11 | Correct | 85 ms | 688 KB | Output is correct |
| 12 | Correct | 85 ms | 684 KB | Output is correct |
| 13 | Correct | 96 ms | 676 KB | Output is correct |
| 14 | Correct | 91 ms | 692 KB | Output is correct |
| 15 | Correct | 85 ms | 696 KB | Output is correct |
| 16 | Correct | 85 ms | 676 KB | Output is correct |
| 17 | Correct | 87 ms | 680 KB | Output is correct |
| 18 | Correct | 86 ms | 672 KB | Output is correct |
| 19 | Correct | 85 ms | 684 KB | Output is correct |
| 20 | Correct | 85 ms | 676 KB | Output is correct |