oj.uz

Submission #28724

# Submission time Handle Problem Language Result Execution time Memory
28724 2017-07-16T11:24:20 Z repeating Paint By Numbers (IOI16_paint) C++11
59 / 100
 13 ms 87376 KB 
#include <bits/stdc++.h>
#include "paint.h"
#define F first
#define S second
#define P push
#define pb push_back
#define MEM(dp,i) memset(dp,i,sizeof(dp))
#define W while
#define R return
#define C continue
#define SI size()
#define ll long long
#define ld long double
#define pll pair<ll,ll>
#define pii pair<int,int>
#define SF(x) scanf("%I64d",&x)
#define SF2(x,y) scanf("%I64d%I64d",&x,&y)
#define SF3(x,y,z) scanf("%I64d%I64d%I64d",&x,&y,&z)
#define SF4(x,y,z,o) scanf("%I64d%I64d%I64d%I64d",&x,&y,&z,&o)
#define all(v) v.begin(),v.end()

using namespace std;
const long long INF = 1e15;
const int MX=200005;

vector<int> c;
string s;
int pr[MX];
int prb[MX];
int k,n;
int dp[MX][105];
int seg(int x,int y){
    if(x>y)R 0;
    int ret=pr[y];
    if(x)ret-=pr[x-1];
    R ret;
}
int segb(int x,int y){
    if(x>y)R 0;
    int ret=prb[y];
    if(x)ret-=prb[x-1];
    R ret;
}
int w[MX];
int b[MX];
int DP(int x,int y){
    if(y==k&&segb(x,n-1)){R 0;}
    if(y==k){w[x]++;R 1;}
    if(x>=n)R 0;
    int &ret=dp[x][y];
    if(ret!=-1)R ret;
    ret=0;
    if(s[x]!='X'){
        ret=DP(x+1,y);
        if(DP(x+1,y)){
            w[x]++;
            w[x+1]--;
        }
    }
    if(seg(x,x+c[y]-1)==0&&x+c[y]-1<n){
        ret=max(ret,DP(x+c[y]+1,y+1));
        if((x+c[y]==n||s[x+c[y]]!='X')&&DP(x+c[y]+1,y+1)){
            w[x+c[y]]++;
            w[x+c[y]+1]--;
            b[x]++;
            b[x+c[y]]--;
        }
    }
//    cout<<x<<" "<<y<<" "<<ret<<endl;
    R ret;
}
string solve_puzzle(string s_, vector<int> c_) {
    s=s_;
    c=c_;
    n=s.SI;
    k=c.SI;
    MEM(dp,-1);
    pr[0]=(s[0]=='_');
    for(int i=1;i<n;i++){
        pr[i]=pr[i-1]+(s[i]=='_');
//        cout<<pr[i];
    }
    prb[0]=(s[0]=='X');
    for(int i=1;i<n;i++){
        prb[i]=prb[i-1]+(s[i]=='X');
    }
    DP(0,0);
    for(int i=1;i<n;i++){
        b[i]+=b[i-1];
        w[i]+=w[i-1];
    }
    string res="";

    for(int i=0;i<n;i++){
        if(b[i]&&w[i]){
            res+='?';
        }
        else if(b[i]){
            res+='X';
        }
        else{
            res+='_';
        }
    }
    return res;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 87376 KB n = 13, m = 1
2 Correct 3 ms 87376 KB n = 18, m = 1
3 Correct 3 ms 87376 KB n = 17, m = 1
4 Correct 6 ms 87376 KB n = 1, m = 1
5 Correct 6 ms 87376 KB n = 20, m = 1
6 Correct 13 ms 87376 KB n = 20, m = 1
7 Correct 6 ms 87376 KB n = 20, m = 1

Subtask #2
3.0 / 3.0

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

Subtask #3
22.0 / 22.0

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

Subtask #4
27.0 / 27.0

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

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 87376 KB n = 13, m = 1
2 Correct 3 ms 87376 KB n = 18, m = 1
3 Correct 3 ms 87376 KB n = 17, m = 1
4 Correct 6 ms 87376 KB n = 1, m = 1
5 Correct 6 ms 87376 KB n = 20, m = 1
6 Correct 13 ms 87376 KB n = 20, m = 1
7 Correct 6 ms 87376 KB n = 20, m = 1
8 Correct 3 ms 87376 KB n = 20, m = 5
9 Correct 6 ms 87376 KB n = 18, m = 3
10 Correct 3 ms 87376 KB n = 17, m = 2
11 Correct 0 ms 87376 KB n = 20, m = 2
12 Correct 6 ms 87376 KB n = 17, m = 4
13 Correct 6 ms 87376 KB n = 17, m = 6
14 Correct 9 ms 87376 KB n = 17, m = 1
15 Correct 6 ms 87376 KB n = 17, m = 4
16 Correct 3 ms 87376 KB n = 13, m = 3
17 Correct 3 ms 87376 KB n = 18, m = 4
18 Correct 6 ms 87376 KB n = 20, m = 10
19 Correct 9 ms 87376 KB n = 19, m = 10
20 Correct 6 ms 87376 KB n = 100, m = 5
21 Correct 13 ms 87376 KB n = 90, m = 3
22 Correct 3 ms 87376 KB n = 86, m = 2
23 Correct 9 ms 87376 KB n = 81, m = 4
24 Correct 9 ms 87376 KB n = 89, m = 10
25 Correct 6 ms 87376 KB n = 81, m = 23
26 Correct 6 ms 87376 KB n = 86, m = 8
27 Correct 6 ms 87376 KB n = 53, m = 22
28 Correct 9 ms 87376 KB n = 89, m = 35
29 Correct 0 ms 87376 KB n = 63, m = 25
30 Correct 6 ms 87376 KB n = 100, m = 50
31 Correct 9 ms 87376 KB n = 99, m = 50
32 Correct 3 ms 87376 KB n = 13, m = 4
33 Correct 6 ms 87376 KB n = 86, m = 2
34 Correct 3 ms 87376 KB n = 88, m = 2
35 Correct 9 ms 87376 KB n = 86, m = 2
36 Correct 6 ms 87376 KB n = 81, m = 6
37 Correct 6 ms 87376 KB n = 98, m = 7
38 Correct 9 ms 87376 KB n = 92, m = 7
39 Correct 6 ms 87376 KB n = 88, m = 21
40 Correct 3 ms 87376 KB n = 90, m = 21
41 Correct 13 ms 87376 KB n = 98, m = 22
42 Correct 3 ms 87376 KB n = 11, m = 2
43 Correct 9 ms 87376 KB n = 11, m = 2
44 Correct 0 ms 87376 KB n = 13, m = 3
45 Correct 6 ms 87376 KB n = 86, m = 2
46 Correct 3 ms 87376 KB n = 81, m = 2
47 Correct 6 ms 87376 KB n = 93, m = 2
48 Correct 3 ms 87376 KB n = 81, m = 2
49 Correct 6 ms 87376 KB n = 86, m = 2
50 Correct 9 ms 87376 KB n = 90, m = 2
51 Correct 9 ms 87376 KB n = 87, m = 2
52 Correct 3 ms 87376 KB n = 97, m = 2
53 Correct 6 ms 87376 KB n = 85, m = 2
54 Correct 9 ms 87376 KB n = 88, m = 7
55 Incorrect 6 ms 87376 KB char #68 differ - expected: '_', found: '?'
56 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 87376 KB n = 13, m = 1
2 Correct 3 ms 87376 KB n = 18, m = 1
3 Correct 3 ms 87376 KB n = 17, m = 1
4 Correct 6 ms 87376 KB n = 1, m = 1
5 Correct 6 ms 87376 KB n = 20, m = 1
6 Correct 13 ms 87376 KB n = 20, m = 1
7 Correct 6 ms 87376 KB n = 20, m = 1
8 Correct 3 ms 87376 KB n = 20, m = 5
9 Correct 6 ms 87376 KB n = 18, m = 3
10 Correct 3 ms 87376 KB n = 17, m = 2
11 Correct 0 ms 87376 KB n = 20, m = 2
12 Correct 6 ms 87376 KB n = 17, m = 4
13 Correct 6 ms 87376 KB n = 17, m = 6
14 Correct 9 ms 87376 KB n = 17, m = 1
15 Correct 6 ms 87376 KB n = 17, m = 4
16 Correct 3 ms 87376 KB n = 13, m = 3
17 Correct 3 ms 87376 KB n = 18, m = 4
18 Correct 6 ms 87376 KB n = 20, m = 10
19 Correct 9 ms 87376 KB n = 19, m = 10
20 Correct 6 ms 87376 KB n = 100, m = 5
21 Correct 13 ms 87376 KB n = 90, m = 3
22 Correct 3 ms 87376 KB n = 86, m = 2
23 Correct 9 ms 87376 KB n = 81, m = 4
24 Correct 9 ms 87376 KB n = 89, m = 10
25 Correct 6 ms 87376 KB n = 81, m = 23
26 Correct 6 ms 87376 KB n = 86, m = 8
27 Correct 6 ms 87376 KB n = 53, m = 22
28 Correct 9 ms 87376 KB n = 89, m = 35
29 Correct 0 ms 87376 KB n = 63, m = 25
30 Correct 6 ms 87376 KB n = 100, m = 50
31 Correct 9 ms 87376 KB n = 99, m = 50
32 Correct 3 ms 87376 KB n = 13, m = 4
33 Correct 6 ms 87376 KB n = 86, m = 2
34 Correct 3 ms 87376 KB n = 88, m = 2
35 Correct 9 ms 87376 KB n = 86, m = 2
36 Correct 6 ms 87376 KB n = 81, m = 6
37 Correct 6 ms 87376 KB n = 98, m = 7
38 Correct 9 ms 87376 KB n = 92, m = 7
39 Correct 6 ms 87376 KB n = 88, m = 21
40 Correct 3 ms 87376 KB n = 90, m = 21
41 Correct 13 ms 87376 KB n = 98, m = 22
42 Correct 3 ms 87376 KB n = 11, m = 2
43 Correct 9 ms 87376 KB n = 11, m = 2
44 Correct 0 ms 87376 KB n = 13, m = 3
45 Correct 6 ms 87376 KB n = 86, m = 2
46 Correct 3 ms 87376 KB n = 81, m = 2
47 Correct 6 ms 87376 KB n = 93, m = 2
48 Correct 3 ms 87376 KB n = 81, m = 2
49 Correct 6 ms 87376 KB n = 86, m = 2
50 Correct 9 ms 87376 KB n = 90, m = 2
51 Correct 9 ms 87376 KB n = 87, m = 2
52 Correct 3 ms 87376 KB n = 97, m = 2
53 Correct 6 ms 87376 KB n = 85, m = 2
54 Correct 9 ms 87376 KB n = 88, m = 7
55 Incorrect 6 ms 87376 KB char #68 differ - expected: '_', found: '?'
56 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 87376 KB n = 13, m = 1
2 Correct 3 ms 87376 KB n = 18, m = 1
3 Correct 3 ms 87376 KB n = 17, m = 1
4 Correct 6 ms 87376 KB n = 1, m = 1
5 Correct 6 ms 87376 KB n = 20, m = 1
6 Correct 13 ms 87376 KB n = 20, m = 1
7 Correct 6 ms 87376 KB n = 20, m = 1
8 Correct 3 ms 87376 KB n = 20, m = 5
9 Correct 6 ms 87376 KB n = 18, m = 3
10 Correct 3 ms 87376 KB n = 17, m = 2
11 Correct 0 ms 87376 KB n = 20, m = 2
12 Correct 6 ms 87376 KB n = 17, m = 4
13 Correct 6 ms 87376 KB n = 17, m = 6
14 Correct 9 ms 87376 KB n = 17, m = 1
15 Correct 6 ms 87376 KB n = 17, m = 4
16 Correct 3 ms 87376 KB n = 13, m = 3
17 Correct 3 ms 87376 KB n = 18, m = 4
18 Correct 6 ms 87376 KB n = 20, m = 10
19 Correct 9 ms 87376 KB n = 19, m = 10
20 Correct 6 ms 87376 KB n = 100, m = 5
21 Correct 13 ms 87376 KB n = 90, m = 3
22 Correct 3 ms 87376 KB n = 86, m = 2
23 Correct 9 ms 87376 KB n = 81, m = 4
24 Correct 9 ms 87376 KB n = 89, m = 10
25 Correct 6 ms 87376 KB n = 81, m = 23
26 Correct 6 ms 87376 KB n = 86, m = 8
27 Correct 6 ms 87376 KB n = 53, m = 22
28 Correct 9 ms 87376 KB n = 89, m = 35
29 Correct 0 ms 87376 KB n = 63, m = 25
30 Correct 6 ms 87376 KB n = 100, m = 50
31 Correct 9 ms 87376 KB n = 99, m = 50
32 Correct 3 ms 87376 KB n = 13, m = 4
33 Correct 6 ms 87376 KB n = 86, m = 2
34 Correct 3 ms 87376 KB n = 88, m = 2
35 Correct 9 ms 87376 KB n = 86, m = 2
36 Correct 6 ms 87376 KB n = 81, m = 6
37 Correct 6 ms 87376 KB n = 98, m = 7
38 Correct 9 ms 87376 KB n = 92, m = 7
39 Correct 6 ms 87376 KB n = 88, m = 21
40 Correct 3 ms 87376 KB n = 90, m = 21
41 Correct 13 ms 87376 KB n = 98, m = 22
42 Correct 3 ms 87376 KB n = 11, m = 2
43 Correct 9 ms 87376 KB n = 11, m = 2
44 Correct 0 ms 87376 KB n = 13, m = 3
45 Correct 6 ms 87376 KB n = 86, m = 2
46 Correct 3 ms 87376 KB n = 81, m = 2
47 Correct 6 ms 87376 KB n = 93, m = 2
48 Correct 3 ms 87376 KB n = 81, m = 2
49 Correct 6 ms 87376 KB n = 86, m = 2
50 Correct 9 ms 87376 KB n = 90, m = 2
51 Correct 9 ms 87376 KB n = 87, m = 2
52 Correct 3 ms 87376 KB n = 97, m = 2
53 Correct 6 ms 87376 KB n = 85, m = 2
54 Correct 9 ms 87376 KB n = 88, m = 7
55 Incorrect 6 ms 87376 KB char #68 differ - expected: '_', found: '?'
56 Halted 0 ms 0 KB -