글 읽기 - 아래 글 쓴 사람입니다. 이번에는 왜 틀렸습니댜 가 나오는지 모르겠습니다.

yjkim9591 1년 전 0

두번째 코드가 시간초과가 뜨는 것을 보고, 이 코드의 시간복잡도를 줄이기 위해 비트연산자를 이용했습니다.
(long long int 를 쓴 이유는 ERROR(ShiftExponent)때문)

for문을 비트연산자로 바꾼 것 밖에 없는데 시간초과가 뜨던게 틀렸습니다.
심지어 시간초과는 18%에서 뜨던게 틀렸습니다는 9%에서 뜹니다.
어떤 테스트케이스가아래에서 잘 작동하던 코드가 비트연산자로 바뀌니까 틀렸다고 출력하는 것 같은데 어디서 틀린건지 모르겠습니다.

채점툴이 틀린건가 싶기도 하고요.

//https://www.acmicpc.net/problem/1849
//틀렸습니다.
#include <stdio.h>
#include <malloc.h>
#include <string.h>

int getAbit(long long int x, int n) { // getbit()
  return (x & (1 << n)) >> n;
}

int main(){
    
    int n,temp,count;
    long long int bit=0;
    scanf("%d",&n);
    
    
    int *before=(int *) malloc (sizeof(int)*n);
    int *after=(int *) malloc (sizeof(int)*n);
    memset(after,0,n);
    
    for(int i=0;i<n;i++)
    {
        scanf("%d",&temp);
        before[i]=temp;
    }
    
    
    for(int i=0;i<n;i++)
    {
        count=0; temp=0;
        while(1)
        {
            if(count==before[i]+1) {after[temp-1]=i+1; bit|=(1<<(temp-1)); break;}
            if(getAbit(bit,temp)==0) {count++; temp++;}
            else temp++;
        }
    }
    
    for(int i=0;i<n;i++)
    {
        printf("%d\n",after[i]); 
    }
    free(before);
    free(after);
    
    return 0;
}


/////////////////////////////////////////////////////////////////////
//ERROR(시간초과)
#include <stdio.h>
#include <malloc.h>
#include <string.h>


int main(){
    
    
    int n,temp,count;
    scanf("%d",&n);
    
    int *before=(int *) malloc (sizeof(int)*n);
    int *after=(int *) malloc (sizeof(int)*n);
    memset(after,0,n);
    
    for(int i=0;i<n;i++)
    {
        scanf("%d",&temp);
        before[i]=temp;
    }
    
    for(int i=0;i<n;i++)
    {
        count=0; temp=0;
        while(1)
        {
            if(count==before[i]+1) {after[temp-1]=i+1; break;}
            if(after[temp]==0) {count++; temp++;}
            else temp++;
        }
    }
    
    for(int i=0;i<n;i++)
    {
        printf("%d ",after[i]); 
    }
    
    free(before);
    free(after);
    
    return 0;
}

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

문제

문제

출처

ICPC

아래 글 쓴 사람입니다. 이번에는 왜 틀렸습니댜 가 나오는지 모르겠습니다.

yjkim9591 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말