글 읽기 - 반례를 못찾겠습니다.

lonecitizen 5년 전 1

다른 댓글에 존재하는 반례들 다 넣어봤는데 다 패스합니다.

30%대에서 실패합니다.

코드가 깔끔하지 못하지만 주석은 최대한 달아봤습니다.

반례 찾아주실분 계시면 좋겠습니다..

#include <stdio.h>
int L, N, vCnt = 0, hCnt = 0;
typedef long long lld;
lld x = 0, y = 0, time = 0, min = 2e9, max = -2e9, vline[500][3], hline[500][3];

int go(lld dist, int head){    
    if(head == 0){//moving horizontally -> only encounter verticals 수평이동 정방향
        for(int j = 0; j < vCnt; j++){
            if(vline[j][0] > x && vline[j][0] <= x + dist){ //이동범위내 수직선 확인
                if(vline[j][1] <= y && vline[j][2] >= y){ //해당수직선 수직범위 확인
                    if(vline[j][0] < min) min = hline[j][0]; //두 조건을 만족하는 수직선중 가장 가까운것
                    if(y == 0 && min > 0) min = 0; //원점이 더 가까울경우
                }
            }
        }
    }else if(head == 2){//수평이동 역방향
        for(int j = 0; j < vCnt; j++){
            if(vline[j][0] >= x - dist && vline[j][0] < x){ //이동범위내 수직선 확인
                if(vline[j][1] <= y && vline[j][2] >= y){ //해당 수직선 수직범위 확인
                    if(vline[j][0] > max) max = vline[j][0]; //두 조건을 만족하는 수직선중 가장 가까운것
                    if(y == 0 && max < 0) max = 0;
                }
            }
        }
    }
    else if(head == 1){//moving vertically -> only encounter horizontals 수직이동 역방향
        for(int j = 0; j < hCnt; j++){
            if(hline[j][0] >= y - dist && hline[j][0] < y){ //수평선 확인
                if(hline[j][1] <= x && hline[j][2] >= x){ //수평범위확인
                    if(hline[j][0] > max) max = hline[j][0]; //가장가까운것
                    if(x == 0 && max < 0) max = 0;
                }
            }
        }
    }
    else{
        for(int j = 0; j < hCnt; j++){ //수직이동 정방향
            if(hline[j][0] > y && hline[j][0] <= y + dist){ //수평선 확인
                if(hline[j][1] <= x && hline[j][2] >= x){ //수평범위확인
                    if(hline[j][0] < min) min = hline[j][0]; //가장가까운것
                    if(x == 0 && min > 0) min = 0;
                } 
            }
        }
    }
   
    if(min != 2e9 || max != -2e9){ //위 로직에서 걸리면 min 또는 max값이 변경됨(수직 혹은 수평선 만났다는 것)
        if(head == 0) time += min - x;
        if(head == 2) time += x - max;
        if(head == 1) time += y - max;
        if(head == 3) time += min - y; //각 이동방향에 따라 가장 가까운 수직 수평선과의 거리를 더해줌
        return 1; //사망 플래그
    }
    if(head == 0) { // 수평선 안만났으면 x y 수평 수직선 업데이트
        hline[hCnt][1] = x;
        x += dist;
        hline[hCnt][0] = y;
        hline[hCnt][2] = x;
        hCnt++;
    }
    else if(head == 1) {
        vline[vCnt][2] = y;
        y -= dist;
        vline[vCnt][0] = x;
        vline[vCnt][1] = y;
        vCnt++;
    }
    else if(head == 2) {
        hline[hCnt][2] = x;
        x -= dist;
        hline[hCnt][0] = y;
        hline[hCnt][1] = x;
        hCnt++;
    }
    else {
        vline[vCnt][1] = y;
        y += dist;
        vline[vCnt][0] = x;
        vline[vCnt][2] = y;
        vCnt++;
    }
    
    // 격자 밖으로 나갔을시 시간 업데이트하고 사망플래그 on
    if(x < -L){
        time += abs( - L - x - dist) + 1;
        return 1;
    }else if(y < -L){
        time += abs(- L - y - dist) + 1;
        return 1;
    }else if(x > L){
        time += abs(L - x + dist) + 1;
        return 1;
    }else if(y > L){
        time += abs(L - y + dist) + 1;
        return 1;
    }
    
    time += dist;
    return 0; //안사망
}
int main(){
    int dist = 0, head = 0;
    char dir;
    scanf("%d %d", &L, &N);
    for(int i = 0; i < N; i++){
        scanf("%d %c ", &dist, &dir);
        if(go(dist, head)){ //회전수만큼 호출하고 죽어서 나오면 로직으로 들어감
            printf("%d", time); 
            return 0;
        }
        if(dir == 'R') head = (head + 1) % 4;      //회전
        else if(dir == 'L') head = (head + 3) % 4;
    }
    go(3e8, head); //더이상 회전이 없고 생존시 3*10^8을 입력으로 넣어 무조건 벽에 부딪히게 만듬
    printf("%d", time);
    return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

반례를 못찾겠습니다.

lonecitizen 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말