oj.uz

답안 #503661

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
503661 2022-01-08T14:40:14 Z doowey 철로 (IOI14_rail) C++14
100 / 100
 289 ms 628 KB 
#include <bits/stdc++.h>
#include "rail.h"

using namespace std;

typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair

const int N = 5010;
int d[N];
bool calc[N];

void findLocation(int n, int first, int location[], int stype[]){
    vector<pii> ord;
    for(int i = 1; i < n; i ++ ){
        d[i] = getDistance(0, i);
        ord.push_back(mp(d[i], i));
    }
    sort(ord.begin(), ord.end());
    location[0] = first;
    stype[0] = 0;
    calc[0]=true;
    int ii = 0;
    int jj;
    int lef, rig;
    int askl, askr;
    int id;
    int pos;
    int dist;
    bool valid;
    int en, st;
    int check;
    int pick;
    for(int i = 0 ; i < ord.size(); i ++ ){
        if(i == 0){
            location[ord[i].se] = first + ord[i].fi;
            stype[ord[i].se] = 1;
            calc[ord[i].se] = true;
            lef = first;
            rig = location[ord[i].se];
            jj = ord[i].se;
        }
        else{
            id = ord[i].se;
            askl = getDistance(ii, id);
            askr = getDistance(jj, id);

            pos = lef + askl;
            pick = -1;

            for(int j = 0 ; j < n; j ++ ){
                if(!calc[j]) continue;
                if(location[j] <= min(pos, rig) && stype[j] == 0){
                    check = (rig - location[j]) + (pos - location[j]);
                    if(check == askr){
                        pick = 0;
                    }
                }
            }
            pos = rig - askr;
            for(int j = 0 ; j < n; j ++ ){
                if(!calc[j]) continue;
                if(location[j] >= max(pos, lef) && stype[j] == 1){
                    check = (location[j] - lef) + (location[j] - pos);
                    if(check == askl){
                        pick = 1;
                    }
                }
            }
            if(pick == -1){
                pos = lef + askl;
                if(d[id] == pos - location[0]){
                    pick = 0;
                }
                else{
                    pick = 1;
                }
            }
            if(pick == 0){
                location[id] = lef + askl;
                stype[id] = 1;
                if(location[id] > rig){
                    rig = location[id];
                    jj = id;
                }
            }
            else{
                location[id] = rig - askr;
                stype[id] = 0;
                if(location[id] < lef){
                    lef = location[id];
                    ii = id;
                }
            }
            calc[id] = true;

        }
    }
    for(int i = 0 ; i < n; i ++ ){
        stype[i] ++ ;
    }

}

Compilation message

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:37:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     for(int i = 0 ; i < ord.size(); i ++ ){
      |                     ~~^~~~~~~~~~~~
rail.cpp:32:9: warning: unused variable 'dist' [-Wunused-variable]
   32 |     int dist;
      |         ^~~~
rail.cpp:33:10: warning: unused variable 'valid' [-Wunused-variable]
   33 |     bool valid;
      |          ^~~~~
rail.cpp:34:9: warning: unused variable 'en' [-Wunused-variable]
   34 |     int en, st;
      |         ^~
rail.cpp:34:13: warning: unused variable 'st' [-Wunused-variable]
   34 |     int en, st;
      |             ^~

Subtask #1
8.0 / 8.0

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

Subtask #2
22.0 / 22.0

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

Subtask #3
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 236 ms 580 KB Output is correct
2 Correct 247 ms 612 KB Output is correct
3 Correct 250 ms 460 KB Output is correct
4 Correct 262 ms 584 KB Output is correct
5 Correct 225 ms 628 KB Output is correct
6 Correct 221 ms 580 KB Output is correct
7 Correct 250 ms 616 KB Output is correct
8 Correct 243 ms 580 KB Output is correct
9 Correct 227 ms 584 KB Output is correct
10 Correct 289 ms 584 KB Output is correct

Subtask #4
44.0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Correct 220 ms 460 KB Output is correct
2 Correct 239 ms 580 KB Output is correct
3 Correct 258 ms 580 KB Output is correct
4 Correct 233 ms 580 KB Output is correct
5 Correct 227 ms 588 KB Output is correct
6 Correct 258 ms 584 KB Output is correct
7 Correct 227 ms 580 KB Output is correct
8 Correct 236 ms 460 KB Output is correct
9 Correct 232 ms 580 KB Output is correct
10 Correct 249 ms 580 KB Output is correct
11 Correct 231 ms 580 KB Output is correct
12 Correct 230 ms 588 KB Output is correct
13 Correct 247 ms 468 KB Output is correct
14 Correct 219 ms 576 KB Output is correct
15 Correct 241 ms 612 KB Output is correct
16 Correct 245 ms 460 KB Output is correct
17 Correct 222 ms 464 KB Output is correct
18 Correct 220 ms 596 KB Output is correct
19 Correct 231 ms 580 KB Output is correct
20 Correct 276 ms 620 KB Output is correct