Submission #24552

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
24552	2017-06-10T12:01:34 Z	Donghyun Kim(#1044)	Paint By Numbers (IOI16_paint)	C++14	59 / 100	19 ms	322924 KB

paint

#include "paint.h"
#include <bits/stdc++.h>
using namespace std;

int n, k, m[102], bl[200002], wh[200002], p[200002][102], ps[200002][102], s[200002][102], ss[200002][102];
char b[200002], ans[200002];

int getb(int s, int e){ return bl[e] - bl[s - 1]; }
int getw(int s, int e){ return wh[e] - wh[s - 1]; }

string solve_puzzle(string str, vector<int> c) {
    n = str.size(); k = c.size();
    for(int i = 1; i <= n; i++) b[i] = str[i - 1];
    for(int i = 1; i <= k; i++) m[i] = c[i - 1];
	for(int i = 1; i <= n; i++){
		bl[i] = bl[i - 1];
		wh[i] = wh[i - 1];
		if(b[i] == 'X') bl[i]++;
		if(b[i] == '_') wh[i]++;
	}
	p[0][0] = ps[0][0] = 1;
    for(int i = 1; i <= n; i++){
		for(int j = 0; j <= k; j++){
			if(b[i] == '_' && j > 0) p[i][j] = 0;
			else if(j == 0) p[i][j] = !getb(1, i);
			else{
				if(getw(i - m[j] + 1, i)) p[i][j] = 0;
				else{
					for(int t = 0; t < i - m[j] + (j == 1); t++){
						if(p[t][j - 1] && !getb(t + 1, i - m[j])){ p[i][j] = 1; break; }
					}
				}
			}
			ps[i][j] = ps[i - 1][j] || p[i][j];
		}
    }
    s[n + 1][k + 1] = ss[n + 1][k + 1] = 1;
    for(int i = n; i >= 1; i--){
		for(int j = k + 1; j >= 1; j--){
			if(b[i] == '_' && j <= k) s[i][j] = 0;
			else if(j > k) s[i][j] = !getb(i, n);
			else{
				if(getw(i, i + m[j] - 1)) s[i][j] = 0;
				else{
					for(int t = n + 1; t > i + m[j] - (j == k); t--){
						if(s[t][j + 1] && !getb(i + m[j], t - 1)){ s[i][j] = 1; break; }
					}
				}
			}
			ss[i][j] = ss[i + 1][j] || s[i][j];
		}
    }
    for(int i = 1; i <= n; i++){
        if(b[i] != '.'){ ans[i] = b[i]; continue; }
        int fl = 0;
        for(int j = 1; j <= k - 1; j++){
			for(int t = i; t <= min(n, i + m[j] - 1); t++){
				for(int y = t + 2; y <= n; y++){
					if(p[t][j] && s[y][j + 1] && !getb(t + 1, y - 1)){ fl = 1; break; }
				}
			}
			if(fl) break;
		}
		for(int t = i; t <= min(n, i + m[k] - 1); t++){
            if(p[t][k] && !getb(t + 1, n)){ fl = 1; break; }
		}
        if(!fl){ ans[i] = '_'; continue; }
        fl = 0;
        if(!getb(i, n) && ps[i - 1][k]) fl = 1;
        if(ss[i + 1][1] && !getb(1, i)) fl = 1;
        for(int x = 1; x < i; x++){
			for(int y = i + 1; y <= n; y++){
				for(int j = 1; j <= k - 1; j++){
					if(p[x][j] && s[y][j + 1] && !getb(x + 1, y - 1)){ fl = 1; break; }
				}
			}
		}
        ans[i] = (fl ? '?' : 'X');
    }
    string ret = (ans + 1);
    return ret;
}

Subtask #1
7.0 / 7.0

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

Subtask #2
3.0 / 3.0

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

Subtask #3
22.0 / 22.0

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

Subtask #4
27.0 / 27.0

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

Subtask #5
0 / 21.0

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

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

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

Submission #24552

Compilation message

Subtask #1 7.0 / 7.0

Subtask #2 3.0 / 3.0

Subtask #3 22.0 / 22.0

Subtask #4 27.0 / 27.0

Subtask #5 0 / 21.0

Subtask #6 0 / 10.0

Subtask #7 0 / 10.0

Subtask #1
7.0 / 7.0

Subtask #2
3.0 / 3.0

Subtask #3
22.0 / 22.0

Subtask #4
27.0 / 27.0

Subtask #5
0 / 21.0

Subtask #6
0 / 10.0

Subtask #7
0 / 10.0