글 읽기 - 반례를 찾아주세요

mc_progw12 3년 전 0

저 코드는 일단 예제에 대해서는 결과가 잘 나옵니다.

그런데 제출을 해보면 2% 쯤에서 틀립니다.

저는 제 논리에서 무엇이 잘못되었는지를 도무지 모르겠습니다.

도움 부탁드립니다.

#include <iostream>
#include <cstdio>
#include <stack>
#include <vector>
#include <algorithm>
#include <stdlib.h>
#include <queue>
#include <string.h>
#include <list>
#include <math.h>
#include <map>
#include <string>
#include <float.h>



using namespace std;





int n,nn,m,p1,p2,t;
pair<int, int> a[1000000]; // (first는 값이고 second는 인덱스입니다)

int f(int x, int y){ // 이게 x~y 범위 내에서 최솟값을 구하는 함수
    pair<int,int> mn; // 이게 답이 될 노드입니다
    while(x<=y){
        if(x%2==1){
            if(!mn.first){ // 답 노드에 값이 없으면 그냥 넣기
                mn.first = a[x].first;
                mn.second = a[x].second;
            }
            else{
                if(mn.first == a[x].first){ // 답 노드와 보고 있는 값이 같으면 둘 중 작은 인덱스를 답 노드에 넣습니다
                    mn.second = min(mn.second,a[x].second);
                }
                if(mn.first > a[x].first){ // 답 노드보다 보고 있는 값이 작으면 넣습니다
                    mn.first = a[x].first;
                    mn.second = a[x].second;
                }
            }
            x++;
        }
        if(y%2==0){ // y도 똑같이 적용
            if(!mn.first){
                mn.first = a[y].first;
                mn.second = a[y].second;
            }
            else{
                if(mn.first == a[y].first){
                    mn.second = min(mn.second,a[y].second);
                }
                if(mn.first > a[y].first){
                    mn.first = a[y].first;
                    mn.second = a[y].second;
                }
            }
            y--;
        }
        x/=2,y/=2;
    }
    return mn.second; // 그리고 답의 인덱스를 리턴합니다
    // 그리고 윗줄에서 mn.first만으로 바꾸면 수쿼 17 코드가 되는데 그렇게 하고 제출해보면 96%에서 틀립니다..
}

int main()
{
    int i,j;
    scanf("%d",&n);
    for(nn=1;nn<=n;nn*=2){}
    nn*=2;
    for(i=nn/2;i<=nn;i++){ // 초기값세팅
        a[i].first = 0x7fffffff; // 값이고요
        a[i].second = i-nn/2+1;  // 인덱스입니다
    }
    for(i=nn/2;i<nn/2+n;i++){ // 입력
        scanf("%d",&a[i].first);
    }
    for(i=nn/2;i<nn/2+n;i++){ // 트리 구현 (모든 가장 아래층 노드에 대해서 쭉 위로 올라가면서 갱신해줍니다)
        j=i/2;
        while(j){
            if(!a[j].first){
                a[j].first = a[i].first;
                a[j].second = a[i].second;
            }
            else{
                if(a[j].first == a[i].first){
                    a[j].first = min(a[i].second,a[j].second);
                }
                if(a[j].first > a[i].first){
                    a[j].first = a[i].first;
                    a[j].second = a[i].second;
                }
            }
            j/=2;
        }
    }

    scanf("%d",&m);
    for(i=0;i<m;i++){
        scanf("%d %d %d",&t,&p1,&p2);
        if(t==2){
            printf("%d\n",f(nn/2+p1-1,nn/2+p2-1));
        }
        else{
            j=nn/2+p1-1;
            a[j].first = p2;

            j/=2;
            while(j){ // 트리 수정 (이번에는 아래에서 두번째 층부터 루트노드까지 [해당 노드] = [아래 두 자식 노드 중 작은 값]을 적용합니다)
                if(a[j*2].first > a[j*2+1].first){
                    a[j].first = a[j*2+1].first;
                    a[j].second = a[j*2+1].second;
                }
                if(a[j*2].first == a[j*2+1].first){
                    a[j].first = a[j*2].first;
                    a[j].second = min(a[j*2].second,a[j*2+1].second);
                }
                if(a[j*2].first < a[j*2+1].first){
                    a[j].first = a[j*2].first;
                    a[j].second = a[j*2].second;
                }
                j/=2;
            }
//            for(j=1;j<=nn;j++){
//                printf("%d{%d} ",a[j].first,a[j].second);
//            }
//            puts("");
        }
    }
}

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

문제

문제

출처

ICPC

반례를 찾아주세요

mc_progw12 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말