Submission #40645

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

paint

#include <bits/stdc++.h>
#include "paint.h"
#include <cstdlib>
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
using namespace std;
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 check(string s,vector<int> c,int k){
    int l = 0;
    int w = 0;
    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)){
            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)){
            l+=c[i]+1;
            w++;
            continue;
        }
        if(s[l] == '_' || s[l] == '.') {
            l++;
            i--;
            continue;
        }
        return false;
    }
   return w == c.size();
}
bool check2(string s,vector<int> c,int j,int k){
    int l = 0;
    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)){
            l+=c[i]+1;
            continue;
        }
        else {
            l++;
            i--;
          continue;
        }
        return false;
    }
    l = k+c[j]+1;
    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)){
            l+=c[i]+1;
            continue;
        }
        else{
            l++;
            i--;
            continue;
        }
        return false;
    }
    return true;
}
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 == 10){
            cout<<0<<endl;
        }*/
        a = check(s,c,i);
        for(int j = 0;j<c.size();j++){
            for(int q = 0;q<s.length();q++){
                int u = q+c[j]-1;
                if(u<s.length() && q<=i && u>=i && checkzero(q,u)){
                    l = q;
                    r = s.length()-u-1;
                    b = check2(s,c,j,q);
                    if(b){
                        break;
                    }
                }
            }
            if(b) break;
        }
        if(a && !b) ans[i] = '_';
        if(!a && b) ans[i] = 'X';
    }
    return ans;
}

Compilation message (stderr)

paint.cpp: In function 'bool check(std::__cxx11::string, std::vector<int>, int)':
paint.cpp:27:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i<c.size();i++){
                    ^
paint.cpp:28:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(l>=s.length()) return false;
             ^
paint.cpp:39: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:51:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    return w == c.size();
             ^
paint.cpp: In function 'bool check2(std::__cxx11::string, std::vector<int>, int, int)':
paint.cpp:56:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(l>=s.length()) return false;
             ^
paint.cpp:69:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = j+1;i<c.size();i++){
                      ^
paint.cpp:70:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(l>=s.length()) return false;
             ^
paint.cpp:71: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:86: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:88:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i<s.length();i++){
                    ^
paint.cpp:92:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i<s.length();i++){
                    ^
paint.cpp:103:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0;j<c.size();j++){
                        ^
paint.cpp:104:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int q = 0;q<s.length();q++){
                            ^
paint.cpp:106:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if(u<s.length() && q<=i && u>=i && checkzero(q,u)){
                     ^
paint.cpp:94:13: warning: variable 'l' set but not used [-Wunused-but-set-variable]
         int l = i;
             ^
paint.cpp:95:13: warning: variable 'r' set but not used [-Wunused-but-set-variable]
         int r = s.length()-i-1;
             ^
paint.cpp:15:11: warning: unused variable 'first' [-Wunused-variable]
 #define f first
           ^
paint.cpp:96: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