oj.uz

Submission #40665

# Submission time Handle Problem Language Result Execution time Memory
40665 2018-02-06T16:45:22 Z legend Paint By Numbers (IOI16_paint) C++14
59 / 100
 6 ms 620 KB 
#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;
    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);

        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;
                    b = check2(s,c,j,q);
                    if(b){
                           // if(i == 0) 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

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:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = j+1;i<c.size();i++){
                      ^
paint.cpp:87:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(l>=s.length()) return false;
             ^
paint.cpp:88: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:108: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:110:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i<s.length();i++){
                    ^
paint.cpp:114:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i<s.length();i++){
                    ^
paint.cpp:126:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0;j<c.size();j++){
                        ^
paint.cpp:127:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int q = 0;q<s.length();q++){
                            ^
paint.cpp:130:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if(u<s.length()-1 && s[u+1] == 'X') continue;
                     ^
paint.cpp:131:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if(u<s.length() && q<=i && u>=i && checkzero(q,u)){
                     ^
paint.cpp:116:13: warning: variable 'l' set but not used [-Wunused-but-set-variable]
         int l = i;
             ^
paint.cpp:117: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:118:14: note: in expansion of macro 'f'
         bool f = true;
              ^

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 248 KB n = 13, m = 1
2 Correct 1 ms 352 KB n = 18, m = 1
3 Correct 1 ms 424 KB n = 17, m = 1
4 Correct 2 ms 500 KB n = 1, m = 1
5 Correct 2 ms 568 KB n = 20, m = 1
6 Correct 2 ms 568 KB n = 20, m = 1
7 Correct 2 ms 604 KB n = 20, m = 1

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 248 KB n = 13, m = 1
2 Correct 1 ms 352 KB n = 18, m = 1
3 Correct 1 ms 424 KB n = 17, m = 1
4 Correct 2 ms 500 KB n = 1, m = 1
5 Correct 2 ms 568 KB n = 20, m = 1
6 Correct 2 ms 568 KB n = 20, m = 1
7 Correct 2 ms 604 KB n = 20, m = 1
8 Correct 2 ms 604 KB n = 20, m = 5
9 Correct 2 ms 604 KB n = 18, m = 3
10 Correct 2 ms 604 KB n = 17, m = 2
11 Correct 2 ms 604 KB n = 20, m = 2
12 Correct 1 ms 604 KB n = 17, m = 4
13 Correct 2 ms 604 KB n = 17, m = 6
14 Correct 1 ms 604 KB n = 17, m = 1
15 Correct 2 ms 604 KB n = 17, m = 4
16 Correct 2 ms 604 KB n = 13, m = 3
17 Correct 1 ms 604 KB n = 18, m = 4
18 Correct 2 ms 604 KB n = 20, m = 10
19 Correct 1 ms 604 KB n = 19, m = 10

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 248 KB n = 13, m = 1
2 Correct 1 ms 352 KB n = 18, m = 1
3 Correct 1 ms 424 KB n = 17, m = 1
4 Correct 2 ms 500 KB n = 1, m = 1
5 Correct 2 ms 568 KB n = 20, m = 1
6 Correct 2 ms 568 KB n = 20, m = 1
7 Correct 2 ms 604 KB n = 20, m = 1
8 Correct 2 ms 604 KB n = 20, m = 5
9 Correct 2 ms 604 KB n = 18, m = 3
10 Correct 2 ms 604 KB n = 17, m = 2
11 Correct 2 ms 604 KB n = 20, m = 2
12 Correct 1 ms 604 KB n = 17, m = 4
13 Correct 2 ms 604 KB n = 17, m = 6
14 Correct 1 ms 604 KB n = 17, m = 1
15 Correct 2 ms 604 KB n = 17, m = 4
16 Correct 2 ms 604 KB n = 13, m = 3
17 Correct 1 ms 604 KB n = 18, m = 4
18 Correct 2 ms 604 KB n = 20, m = 10
19 Correct 1 ms 604 KB n = 19, m = 10
20 Correct 2 ms 604 KB n = 100, m = 5
21 Correct 6 ms 608 KB n = 90, m = 3
22 Correct 2 ms 608 KB n = 86, m = 2
23 Correct 2 ms 608 KB n = 81, m = 4
24 Correct 3 ms 620 KB n = 89, m = 10
25 Correct 3 ms 620 KB n = 81, m = 23
26 Correct 2 ms 620 KB n = 86, m = 8
27 Correct 2 ms 620 KB n = 53, m = 22
28 Correct 4 ms 620 KB n = 89, m = 35
29 Correct 3 ms 620 KB n = 63, m = 25
30 Correct 4 ms 620 KB n = 100, m = 50
31 Correct 5 ms 620 KB n = 99, m = 50

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 248 KB n = 13, m = 1
2 Correct 1 ms 352 KB n = 18, m = 1
3 Correct 1 ms 424 KB n = 17, m = 1
4 Correct 2 ms 500 KB n = 1, m = 1
5 Correct 2 ms 568 KB n = 20, m = 1
6 Correct 2 ms 568 KB n = 20, m = 1
7 Correct 2 ms 604 KB n = 20, m = 1
8 Correct 2 ms 604 KB n = 20, m = 5
9 Correct 2 ms 604 KB n = 18, m = 3
10 Correct 2 ms 604 KB n = 17, m = 2
11 Correct 2 ms 604 KB n = 20, m = 2
12 Correct 1 ms 604 KB n = 17, m = 4
13 Correct 2 ms 604 KB n = 17, m = 6
14 Correct 1 ms 604 KB n = 17, m = 1
15 Correct 2 ms 604 KB n = 17, m = 4
16 Correct 2 ms 604 KB n = 13, m = 3
17 Correct 1 ms 604 KB n = 18, m = 4
18 Correct 2 ms 604 KB n = 20, m = 10
19 Correct 1 ms 604 KB n = 19, m = 10
20 Correct 2 ms 604 KB n = 100, m = 5
21 Correct 6 ms 608 KB n = 90, m = 3
22 Correct 2 ms 608 KB n = 86, m = 2
23 Correct 2 ms 608 KB n = 81, m = 4
24 Correct 3 ms 620 KB n = 89, m = 10
25 Correct 3 ms 620 KB n = 81, m = 23
26 Correct 2 ms 620 KB n = 86, m = 8
27 Correct 2 ms 620 KB n = 53, m = 22
28 Correct 4 ms 620 KB n = 89, m = 35
29 Correct 3 ms 620 KB n = 63, m = 25
30 Correct 4 ms 620 KB n = 100, m = 50
31 Correct 5 ms 620 KB n = 99, m = 50
32 Correct 1 ms 620 KB n = 13, m = 4
33 Correct 1 ms 620 KB n = 86, m = 2
34 Correct 2 ms 620 KB n = 88, m = 2
35 Correct 2 ms 620 KB n = 86, m = 2
36 Correct 2 ms 620 KB n = 81, m = 6
37 Correct 2 ms 620 KB n = 98, m = 7
38 Correct 2 ms 620 KB n = 92, m = 7
39 Correct 2 ms 620 KB n = 88, m = 21
40 Correct 2 ms 620 KB n = 90, m = 21
41 Correct 2 ms 620 KB n = 98, m = 22

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 248 KB n = 13, m = 1
2 Correct 1 ms 352 KB n = 18, m = 1
3 Correct 1 ms 424 KB n = 17, m = 1
4 Correct 2 ms 500 KB n = 1, m = 1
5 Correct 2 ms 568 KB n = 20, m = 1
6 Correct 2 ms 568 KB n = 20, m = 1
7 Correct 2 ms 604 KB n = 20, m = 1
8 Correct 2 ms 604 KB n = 20, m = 5
9 Correct 2 ms 604 KB n = 18, m = 3
10 Correct 2 ms 604 KB n = 17, m = 2
11 Correct 2 ms 604 KB n = 20, m = 2
12 Correct 1 ms 604 KB n = 17, m = 4
13 Correct 2 ms 604 KB n = 17, m = 6
14 Correct 1 ms 604 KB n = 17, m = 1
15 Correct 2 ms 604 KB n = 17, m = 4
16 Correct 2 ms 604 KB n = 13, m = 3
17 Correct 1 ms 604 KB n = 18, m = 4
18 Correct 2 ms 604 KB n = 20, m = 10
19 Correct 1 ms 604 KB n = 19, m = 10
20 Correct 2 ms 604 KB n = 100, m = 5
21 Correct 6 ms 608 KB n = 90, m = 3
22 Correct 2 ms 608 KB n = 86, m = 2
23 Correct 2 ms 608 KB n = 81, m = 4
24 Correct 3 ms 620 KB n = 89, m = 10
25 Correct 3 ms 620 KB n = 81, m = 23
26 Correct 2 ms 620 KB n = 86, m = 8
27 Correct 2 ms 620 KB n = 53, m = 22
28 Correct 4 ms 620 KB n = 89, m = 35
29 Correct 3 ms 620 KB n = 63, m = 25
30 Correct 4 ms 620 KB n = 100, m = 50
31 Correct 5 ms 620 KB n = 99, m = 50
32 Correct 1 ms 620 KB n = 13, m = 4
33 Correct 1 ms 620 KB n = 86, m = 2
34 Correct 2 ms 620 KB n = 88, m = 2
35 Correct 2 ms 620 KB n = 86, m = 2
36 Correct 2 ms 620 KB n = 81, m = 6
37 Correct 2 ms 620 KB n = 98, m = 7
38 Correct 2 ms 620 KB n = 92, m = 7
39 Correct 2 ms 620 KB n = 88, m = 21
40 Correct 2 ms 620 KB n = 90, m = 21
41 Correct 2 ms 620 KB n = 98, m = 22
42 Incorrect 2 ms 620 KB char #8 differ - expected: '?', found: '_'
43 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 248 KB n = 13, m = 1
2 Correct 1 ms 352 KB n = 18, m = 1
3 Correct 1 ms 424 KB n = 17, m = 1
4 Correct 2 ms 500 KB n = 1, m = 1
5 Correct 2 ms 568 KB n = 20, m = 1
6 Correct 2 ms 568 KB n = 20, m = 1
7 Correct 2 ms 604 KB n = 20, m = 1
8 Correct 2 ms 604 KB n = 20, m = 5
9 Correct 2 ms 604 KB n = 18, m = 3
10 Correct 2 ms 604 KB n = 17, m = 2
11 Correct 2 ms 604 KB n = 20, m = 2
12 Correct 1 ms 604 KB n = 17, m = 4
13 Correct 2 ms 604 KB n = 17, m = 6
14 Correct 1 ms 604 KB n = 17, m = 1
15 Correct 2 ms 604 KB n = 17, m = 4
16 Correct 2 ms 604 KB n = 13, m = 3
17 Correct 1 ms 604 KB n = 18, m = 4
18 Correct 2 ms 604 KB n = 20, m = 10
19 Correct 1 ms 604 KB n = 19, m = 10
20 Correct 2 ms 604 KB n = 100, m = 5
21 Correct 6 ms 608 KB n = 90, m = 3
22 Correct 2 ms 608 KB n = 86, m = 2
23 Correct 2 ms 608 KB n = 81, m = 4
24 Correct 3 ms 620 KB n = 89, m = 10
25 Correct 3 ms 620 KB n = 81, m = 23
26 Correct 2 ms 620 KB n = 86, m = 8
27 Correct 2 ms 620 KB n = 53, m = 22
28 Correct 4 ms 620 KB n = 89, m = 35
29 Correct 3 ms 620 KB n = 63, m = 25
30 Correct 4 ms 620 KB n = 100, m = 50
31 Correct 5 ms 620 KB n = 99, m = 50
32 Correct 1 ms 620 KB n = 13, m = 4
33 Correct 1 ms 620 KB n = 86, m = 2
34 Correct 2 ms 620 KB n = 88, m = 2
35 Correct 2 ms 620 KB n = 86, m = 2
36 Correct 2 ms 620 KB n = 81, m = 6
37 Correct 2 ms 620 KB n = 98, m = 7
38 Correct 2 ms 620 KB n = 92, m = 7
39 Correct 2 ms 620 KB n = 88, m = 21
40 Correct 2 ms 620 KB n = 90, m = 21
41 Correct 2 ms 620 KB n = 98, m = 22
42 Incorrect 2 ms 620 KB char #8 differ - expected: '?', found: '_'
43 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 248 KB n = 13, m = 1
2 Correct 1 ms 352 KB n = 18, m = 1
3 Correct 1 ms 424 KB n = 17, m = 1
4 Correct 2 ms 500 KB n = 1, m = 1
5 Correct 2 ms 568 KB n = 20, m = 1
6 Correct 2 ms 568 KB n = 20, m = 1
7 Correct 2 ms 604 KB n = 20, m = 1
8 Correct 2 ms 604 KB n = 20, m = 5
9 Correct 2 ms 604 KB n = 18, m = 3
10 Correct 2 ms 604 KB n = 17, m = 2
11 Correct 2 ms 604 KB n = 20, m = 2
12 Correct 1 ms 604 KB n = 17, m = 4
13 Correct 2 ms 604 KB n = 17, m = 6
14 Correct 1 ms 604 KB n = 17, m = 1
15 Correct 2 ms 604 KB n = 17, m = 4
16 Correct 2 ms 604 KB n = 13, m = 3
17 Correct 1 ms 604 KB n = 18, m = 4
18 Correct 2 ms 604 KB n = 20, m = 10
19 Correct 1 ms 604 KB n = 19, m = 10
20 Correct 2 ms 604 KB n = 100, m = 5
21 Correct 6 ms 608 KB n = 90, m = 3
22 Correct 2 ms 608 KB n = 86, m = 2
23 Correct 2 ms 608 KB n = 81, m = 4
24 Correct 3 ms 620 KB n = 89, m = 10
25 Correct 3 ms 620 KB n = 81, m = 23
26 Correct 2 ms 620 KB n = 86, m = 8
27 Correct 2 ms 620 KB n = 53, m = 22
28 Correct 4 ms 620 KB n = 89, m = 35
29 Correct 3 ms 620 KB n = 63, m = 25
30 Correct 4 ms 620 KB n = 100, m = 50
31 Correct 5 ms 620 KB n = 99, m = 50
32 Correct 1 ms 620 KB n = 13, m = 4
33 Correct 1 ms 620 KB n = 86, m = 2
34 Correct 2 ms 620 KB n = 88, m = 2
35 Correct 2 ms 620 KB n = 86, m = 2
36 Correct 2 ms 620 KB n = 81, m = 6
37 Correct 2 ms 620 KB n = 98, m = 7
38 Correct 2 ms 620 KB n = 92, m = 7
39 Correct 2 ms 620 KB n = 88, m = 21
40 Correct 2 ms 620 KB n = 90, m = 21
41 Correct 2 ms 620 KB n = 98, m = 22
42 Incorrect 2 ms 620 KB char #8 differ - expected: '?', found: '_'
43 Halted 0 ms 0 KB -