Submission #436046

#	Time	Username	Problem	Language	Result	Execution time	Memory
436046		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++) 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;
        }

        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]=='_'){

                flag = 1, cur = j; break;
            }
            if (!flag) break;
        }

        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] = 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:21:18: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
   21 |             if (r-cur>=a[s]){
      |                 ~^~~~
paint.cpp:20:9: warning: 'l' may be used uninitialized in this function [-Wmaybe-uninitialized]
   20 |         if (cur!=l){
      |         ^~

• 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