Submission #436038

#	Time	Username	Problem	Language	Result	Execution time	Memory
436038		qwerasdfzxcl	Paint By Numbers (IOI16_paint)	C++14	32 / 100	1 ms	328 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){
            if (l-1>=0){
                if (!ans[l-1] || ans[l-1]=='_') ans[l-1] = '_';
                else ans[l-1] = '?';
            }
            if (r<(int)ans.size()){
                if (!ans[r] || ans[r]=='_') ans[r] = '_';
                else ans[r] = '?';
            }

        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 = cur+1;
            }
            cur = i+1;
        }
        if (cur!=l){
            if (r-cur>=a[s]){
                cnt++;
                idx1 = cur, idx2 = cur+1;
            }
            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]=='_'){
                for (int k=cur;k<j;k++){
                    if (!ans[k] || ans[k]=='_') ans[k] = '_';
                    else ans[k] = '?';
                }
                flag = 1, cur = j+1; break;
            }
            if (!flag) break;
        }
        if (!ans[cur+a[i]] || ans[cur+a[i]]=='_') ans[cur+a[i]] = '_';
        else ans[cur+a[i]] = '?';
        cur += a[i]+1;
    }
    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]=='_'){
                for (int k=cur-1;k>=j;k--){
                    if (!ans[k] || ans[k]=='_') ans[k] = '_';
                    else ans[k] = '?';
                }
                flag = 1, cur = j; break;
            }
            if (!flag) break;
        }
        if (!ans[cur-a[i]-1] || ans[cur-a[i]-1]=='_') ans[cur-a[i]-1] = '_';
        else ans[cur-a[i]-1] = '?';
        cur -= a[i]+1;

    }
    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] = '_';
    dnc(0, n, 0, m);
    return ans;
}

Compilation message (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: 0 / 27
• Subtask 5: 0 / 21
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10