Submission #436076

#	Time	Username	Problem	Language	Result	Execution time	Memory
436076		qwerasdfzxcl	Paint By Numbers (IOI16_paint)	C++14	7 / 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 LL = -1, RR = -1;
        for (int i=l;i<r;i++) if (str[i]=='X'){
            if (LL==-1) LL = i;
            RR = i;
        }
        if (LL!=-1){
        int L2 = max(RR-a[s]+1, l), R2 = min(LL+a[s], r);
        for (int i=LL-1;i>=L2;i--) if (str[i]=='_'){
            L2 = i+1; break;
        }
        for (int i=RR+1;i<R2;i++) if (str[i]=='_'){
            R2 = i; break;
        }
        if (l!=L2 || r!=R2){
            dnc(L2, R2, s, e); return;
        }}

        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++) ans[j] = '?';
                    }
                    else{
                        for (int j=cur;j<i;j++){
                            if (!ans[j] || ans[j]=='_') ans[j] = '_';
                            else ans[j] = '?';
                        }
                    }
                    cur = i+1;
                }
                int i = r;
                    if (i-cur>=a[s]){
                        for (int j=cur;j<i;j++) ans[j] = '?';
                    }
                    else{
                        for (int j=cur;j<i;j++){
                            if (!ans[j] || ans[j]=='_') ans[j] = '_';
                            else 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 ans[i] = '?';
                }
                return;
            }
            for (int i=l;i<r;i++){
                if (r-a[s]<=i && i<l+a[s]){
                    if (!ans[i] || ans[i]=='X') ans[i] = 'X';
                    else ans[i] = '?';
                }
                else 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(ans[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(cur, 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(ans[cur+a[i]]=='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, cur, 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] = '_';
    return ans;
}

Compilation message (stderr)

paint.cpp: In function 'void dnc(int, int, int, int)':
paint.cpp:73:18: warning: 'idx2' may be used uninitialized in this function [-Wmaybe-uninitialized]
   73 |             if (r-l<a[s]){
      |                 ~^~
paint.cpp:37:9: warning: 'idx1' may be used uninitialized in this function [-Wmaybe-uninitialized]
   37 |         if (cur!=l){
      |         ^~
paint.cpp:128:8: warning: 'l' may be used uninitialized in this function [-Wmaybe-uninitialized]
  128 |     dnc(cur, r, m, e);
      |     ~~~^~~~~~~~~~~~~~

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