Submission #40667

#	Time	Username	Problem	Language	Result	Execution time	Memory
40667		legend	Paint By Numbers (IOI16_paint)	C++14	59 / 100	6 ms	620 KiB

paint

#include <bits/stdc++.h>
#include "paint.h"
#include <cstdlib>
using namespace std;
typedef long long int ll ;
#define sc(n) scanf("%d" , &n);
#define scl(n) scanf("%lld" , &n);
#define pi(n) printf("%d" , n);
#define pil(n) printf("%lld" , n);
#define pn() printf("\n");
#define mp(a,b) make_pair(a,b)
#define pb push_back
#define rep(i,a,n) for( int i = a ; i < n ; i++ )
#define rev(i , n) for( int i = n ; i >= 0 ; i--)
#define s second
#define f first
const int N = 107;
int pref[N];
bool checkzero(int l,int r){
    int x = pref[r];
    if(l) x-=pref[l-1];
    return x == 0;
}
bool checkcnt(int cnt,string s){
    int as = 0;
    for(int i = 1;i<s.length();i++) if(s[i-1] == 'X' && s[i]!=s[i-1]) as++;
    if(s[s.length()-1] == 'X') as++;
    return as == cnt;
}
bool check(string s,vector<int> c,int k){
    int l = 0;
    int w = 0;
    string ss = s;
    for(int i = 0;i<c.size();i++){
        if(l>=s.length()) return false;
        if(l+c[i]-1<k && checkzero(l,l+c[i]-1)){
            for(int jj = l;jj<=l+c[i]-1;jj++) ss[jj] = 'X';
            l+=c[i]+1;
            w++;
            continue;
        }
        if(l == k) {
            l++;
            i--;
            continue;
        }
        if(l>k && l+c[i]-1<s.length() && checkzero(l,l+c[i]-1)){
            for(int jj = l;jj<=l+c[i]-1;jj++) ss[jj] = 'X';
            l+=c[i]+1;
            w++;
            continue;
        }
        if(s[l] == '_' || s[l] == '.') {
            l++;
            i--;
            continue;
        }
        return false;
    }
   // cout<<ss<<endl;
   return checkcnt(c.size(),ss);
}
bool check2(string s,vector<int> c,int j,int k){
    int l = 0;
    string ss = s;
    for(int i = k;i<=k+c[j]-1;i++) ss[i] = 'X';
    pref[0] = ss[0] == '_';
    for(int i = 1;i<ss.length();i++) pref[i] = pref[i-1]+(ss[i] == '_');
    int w = 1;
    for(int i = 0;i<j;i++) {
        if(l>=s.length()) return false;
        if(l+c[i]-1<k-1 && checkzero(l,l+c[i]-1)){
                for(int jj = l;jj<=l+c[i]-1;jj++) ss[jj] = 'X';
                w++;
            l+=c[i]+1;
            continue;
        }
        else {
            l++;
            i--;
          continue;
        }
        return false;
    }
    l = k+c[j]+1;
    if(l<s.length()){
    for(int i = j+1;i<c.size();i++){
        if(l>=s.length()) return false;
        if(l+c[i]-1<s.length() && checkzero(l,l+c[i]-1)){
            for(int jj = l;jj<=l+c[i]-1;jj++) ss[jj] = 'X';
            l+=c[i]+1;
            w++;
            continue;
        }
        else{
            l++;
            i--;
            continue;
        }
        return false;
    }
    /*if(k == 0 && j == 0){
        cout<<ss<<endl;
    }*/
    }
    return checkcnt(c.size(),ss);
}
std::string solve_puzzle(std::string s, std::vector<int> c) {
    pref[0] = s[0] == '_';
    for(int i = 1;i<s.length();i++) pref[i] = pref[i-1]+(s[i] == '_');
    string ans;
    for(int i = 0;i<s.length();i++){
     if(s[i] == '.')    ans+="?";
     else ans+=s[i];
    }
    for(int i = 0;i<s.length();i++){
        if(s[i]!='.') continue;
        int l = i;
        int r = s.length()-i-1;
        bool f = true;
        bool a,b;
        a = b = false;
        /*if(i == 3){
            cout<<0<<endl;
        }*/
        a = check(s,c,i);
        /*if(i == 8){
            cout<<a<<endl;

        }*/
        for(int j = 0;j<c.size();j++){
            for(int q = 0;q<s.length();q++){
                int u = q+c[j]-1;
                if(q && s[q-1] == 'X') continue;
                if(u<s.length()-1 && s[u+1] == 'X') continue;
                if(u<s.length() && q<=i && u>=i && checkzero(q,u)){
                    l = q;
                    r = s.length()-u-1;
           /*         if(l == 8 && u == 9){
                        cout<<1<<endl;

                    }*/
                    b = check2(s,c,j,q);
                    if(b){
                           // if(i == 8) cout<<j<<" "<<q<<endl;
                        break;
                    }
                }
            }
            if(b) break;
        }
        /*if(i == 3){
            cout<<a <<endl;
        }*/
        if(a && !b) ans[i] = '_';
        if(!a && b) ans[i] = 'X';
    }
    return ans;
}

Compilation message (stderr)

paint.cpp: In function 'bool checkcnt(int, std::__cxx11::string)':
paint.cpp:26:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 1;i<s.length();i++) if(s[i-1] == 'X' && s[i]!=s[i-1]) as++;
                    ^
paint.cpp: In function 'bool check(std::__cxx11::string, std::vector<int>, int)':
paint.cpp:34:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i<c.size();i++){
                    ^
paint.cpp:35:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(l>=s.length()) return false;
             ^
paint.cpp:47:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(l>k && l+c[i]-1<s.length() && checkzero(l,l+c[i]-1)){
                           ^
paint.cpp: In function 'bool check2(std::__cxx11::string, std::vector<int>, int, int)':
paint.cpp:68:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 1;i<ss.length();i++) pref[i] = pref[i-1]+(ss[i] == '_');
                    ^
paint.cpp:71:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(l>=s.length()) return false;
             ^
paint.cpp:86:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(l<s.length()){
         ^
paint.cpp:87:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = j+1;i<c.size();i++){
                      ^
paint.cpp:88:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(l>=s.length()) return false;
             ^
paint.cpp:89:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(l+c[i]-1<s.length() && checkzero(l,l+c[i]-1)){
                    ^
paint.cpp: In function 'std::__cxx11::string solve_puzzle(std::__cxx11::string, std::vector<int>)':
paint.cpp:110:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 1;i<s.length();i++) pref[i] = pref[i-1]+(s[i] == '_');
                    ^
paint.cpp:112:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i<s.length();i++){
                    ^
paint.cpp:116:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i<s.length();i++){
                    ^
paint.cpp:131:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0;j<c.size();j++){
                        ^
paint.cpp:132:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int q = 0;q<s.length();q++){
                            ^
paint.cpp:135:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if(u<s.length()-1 && s[u+1] == 'X') continue;
                     ^
paint.cpp:136:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if(u<s.length() && q<=i && u>=i && checkzero(q,u)){
                     ^
paint.cpp:118:13: warning: variable 'l' set but not used [-Wunused-but-set-variable]
         int l = i;
             ^
paint.cpp:119:13: warning: variable 'r' set but not used [-Wunused-but-set-variable]
         int r = s.length()-i-1;
             ^
paint.cpp:16:11: warning: unused variable 'first' [-Wunused-variable]
 #define f first
           ^
paint.cpp:120:14: note: in expansion of macro 'f'
         bool f = true;
              ^

• 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