제출 #436096

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
436096		qwerasdfzxcl	Paint By Numbers (IOI16_paint)	C++14	59 / 100	1 ms	204 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
string str, ans;
vector<int> a;

void dnc(int l, int r, int s, int e){
    //printf("%d %d %d %d\n", l, r, s, e);
    if (e-s==1){

        int cur = l, cnt = 0, idx1, idx2;
        for (int i=l;i<r;i++) if (str[i]=='_'){
            if (i-cur>=a[s]){
                cnt++;
                idx1 = cur, idx2 = i;
            }
            cur = i+1;
        }
        if (cur!=l){
            if (r-cur>=a[s]){
                cnt++;
                idx1 = cur, idx2 = r;
            }
            if (cnt>=2){
                cur = l;
                for (int i=l;i<r;i++) if (str[i]=='_'){
                    if (i-cur>=a[s]){
                        for (int j=cur;j<i;j++){
                            if (str[j]!='X') ans[j] = '?';
                        }
                    }
                    else{
                        for (int j=cur;j<i;j++){
                            if (!ans[j] || ans[j]=='_') ans[j] = '_';
                            else if (str[j]!='X') ans[j] = '?';
                        }
                    }
                    cur = i+1;
                }
                int i = r;
                    if (i-cur>=a[s]){
                        for (int j=cur;j<i;j++) if (str[j]!='X') ans[j] = '?';
                    }
                    else{
                        for (int j=cur;j<i;j++){
                            if (!ans[j] || ans[j]=='_') ans[j] = '_';
                            else if (str[j]!='X') ans[j] = '?';
                        }
                    }
            }
            else{
                assert(cnt==1);
                dnc(idx1, idx2, s, e);
            }
        }
        else{
            if (r-l<a[s]){
                for (int i=l;i<r;i++){
                    if (!ans[i] || ans[i]=='_') ans[i] = '_';
                    else if (str[i]!='X') ans[i] = '?';
                }
                return;
            }
            int asdf = -1, qwer = -1;
            for (int i=l;i<=r-a[s];i++){
                if ((i-1<l || str[i-1]!='X') && (i+a[s]>=r || str[i+a[s]]!='X')){
                    if (asdf==-1) asdf = i;
                    qwer = i;
                }
            }
            //printf("%d %d\n", asdf, qwer);
            if (asdf==-1){
                for (int i=l;i<r;i++){
                    if (!ans[i] || ans[i]=='_') ans[i] = '_';
                    else if (str[i]!='X') ans[i] = '?';
                }
                return;
            }
            for (int i=l;i<r;i++){
                if (qwer<=i && i<asdf+a[s]){
                    if (!ans[i] || ans[i]=='X') ans[i] = 'X';
                    else if (str[i]!='X') ans[i] = '?';
                }
                else if (str[i]!='X') ans[i] = '?';
            }
        }
        return;
    }

    int m = (s+e)>>1, cur = l;
    for (int i=s;i<m;i++){
        while(true){
            bool flag = 0;
            for (int j=cur;j<cur+a[i];j++) if (str[j]=='_'){
                flag = 1, cur = j+1; break;
            }
            if (!flag) break;
        }
        while(str[cur+a[i]]=='X') cur++;
        cur += a[i]+1;
    }
    int cur2 = r-1;
    for (int i=e-1;i>=m;i--){
        bool flag = 0;
        for (int j=cur2;j>=l+a[i]-1;j--) if (str[j]=='X'){
            flag = 1;
            bool chk = 0;
            for (int k=j;k>=j-a[i]+1;k--) if (str[k]=='_'){
                chk = 1;
                bool chk2 = 0;
                for (int l=k+1;l<=k+a[i];l++) if (str[l]=='_'){
                    chk2 = 1, cur2 = l-1; break;
                }
                if (!chk2) cur2 = k-1;
                break;
            }
            if (chk) break;
            while(j-a[i]>=l && str[j-a[i]]=='X' && str[j+1]!='_' && j+1<=cur2) j++;
            if (j<=cur2 && (j-a[i]<l || str[j-a[i]]!='X') && str[j]!='_') cur2 = j-a[i]-1;
            else cur2 = j-1;
            break;
        }
        if (!flag){
            cur2 = l-2; break;
        }
    }
    dnc(max(cur, cur2+2), r, m, e);


    cur = r;
    for (int i=e-1;i>=m;i--){
        while(true){
            bool flag = 0;
            for (int j=cur-1;j>=cur-a[i];j--) if (str[j]=='_'){

                flag = 1, cur = j; break;
            }
            if (!flag) break;
        }
        while(str[cur-a[i]-1]=='X') cur--;
        cur -= a[i]+1;
    }

    cur2 = l;
    for (int i=s;i<m;i++){
        bool flag = 0;
        for (int j=cur2;j<=r-a[i];j++) if (str[j]=='X'){
            flag = 1;
            bool chk = 0;
            for (int k=j;k<=j+a[i]-1;k++) if (str[k]=='_'){
                chk = 1;
                bool chk2 = 0;
                for (int l=k-1;l>=k-a[i];l--) if (str[l]=='_'){
                    chk2 = 1, cur2 = l+1; break;
                }
                if (!chk2) cur2 = k+1;
                break;
            }
            if (chk) break;
            while(j+a[i]<r && str[j+a[i]]=='X' && str[j-1]!='_' && j-1>=cur2) j--;
            if (j>=cur2 && (j+a[i]<r || str[j+a[i]]!='X') && str[j]!='_') cur2 = j+a[i]+1;
            else cur2 = j+1;
            break;
        }
        if (!flag){
            cur2 = r+1; break;
        }
    }
    dnc(l, min(cur, cur2-1), s, m);
}

string solve_puzzle(string s, vector<int> c) {
    str = s, a = c;
    int n = s.size(), m = c.size();
    ans.resize(s.size());
    for (int i=0;i<n;i++) if (str[i]!='.') ans[i] = str[i];
    dnc(0, n, 0, m);
  	for (int i=0;i<n;i++) if (!ans[i]) ans[i] = '_';
  	for (int i=0;i<n;i++) assert(str[i]!='X' || ans[i]=='X');
    return ans;
}

컴파일 시 표준 에러 (stderr) 메시지

paint.cpp: In function 'void dnc(int, int, int, int)':
paint.cpp:9:21: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
    9 | void dnc(int l, int r, int s, int e){
      |                 ~~~~^
paint.cpp:9:14: warning: 'l' may be used uninitialized in this function [-Wmaybe-uninitialized]
    9 | void dnc(int l, int r, int s, int e){
      |          ~~~~^

• Subtask 1: 7 / 7
• Subtask 2: 3 / 3
• Subtask 3: 22 / 22
• Subtask 4: 27 / 27
• Subtask 5: 0 / 21
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10