글 읽기 - 틀린이유가 무엇인가요..

kyo20111 4년 전 0

p[i]에는 i번째 수보다 작은 수의 개수가 들어있습니다.

코드를 갈아엎고 풀어냈지만 여전히 전 풀이의 틀린점을 모르겠습니다 ㅜㅜ

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int t,n,arr[111],p[111],ans[111],chk[111];
pair<int,int> pr[111];
bool comp(pair<int,int> a,pair<int,int> b){
    return pair<int,int>(a.first,b.second) > pair<int,int>(b.first,a.second);
}
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        for(int i=1;i<=n;i++) scanf("%d",&arr[i]);
        for(int i=1;i<=n;i++) pr[i]={arr[i],i};
        for(int i=1;i<=n;i++) p[i]=0,chk[i]=0;
        int fl=0;
        for(int i=1;i<=n;i++){
            if(arr[i] >= i){ // arr[i] 보다 작은 수의 개수가 i보다 크거나 같으면 IMPOSSIBLE
                printf("IMPOSSIBLE\n");
                fl=1;
                break;
            }

            if(i > 1){
                sort(pr+1,pr+i,comp);
                p[i] += arr[i]; // i번째 수 보다 앞에 있으면서 i보다 작은 수의 개수
                for(int j=1;j<i-arr[i];j++) p[pr[j].second]++; //i번째 수보다 앞에 있는 j번째 수가 i번째 수 보다 클 때 표시
            }
        }
        if(fl) continue;

        for(int i=1;i<=n;i++){
            if(chk[p[i]+1]){
                printf("IMPOSSIBLE\n");
                fl=1;
                break;
            }
            chk[p[i]+1]=1;
            ans[i] = p[i]+1;
        }
        if(fl) continue;

        for(int i=1;i<=n;i++) printf("%d ",ans[i]);
        puts("");
    }
}

chogahui05 4년 전 1

풀이의 틀린점은 코드를 더 분석을 해 봐야 될 듯 싶고요..

반례만 드리겠습니다.

1
10
0 0 0 1 3 2 4 0 0 1

    
ans
10 7 4 5 9 6 8 3 1 2

sait2000 4년 전 1

으으 스트레서 짜고 있었는데 ㅠㅠ 일단 반례를 줄여봤습니다.

in:
1
4
0 0 1 2

out:
4 1 2 3

kyo20111 4년 전 0

두분 감사합니다 반례 보면서 코드 잘못된점을 찾아봐야겠네요

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

문제

문제

출처

ICPC

틀린이유가 무엇인가요..

kyo20111 4년 전 0

chogahui05 4년 전 1

sait2000 4년 전 1

kyo20111 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말