oj.uz

Submission #43090

# Submission time Handle Problem Language Result Execution time Memory
43090 2018-03-09T02:23:17 Z MatheusLealV Paint By Numbers (IOI16_paint) C++14
32 / 100
 4 ms 1608 KB 
#include <bits/stdc++.h>
#include "paint.h"
#define K 120
#define N 200050
using namespace std;

int ini[K], fim[K], n, sz[K], cnt[N], global[N];

char v[N];

int g(char c){
	if(c == '.') return 0;
	if(c == 'X') return 1;
	if(c == '_') return -1;
}

string solve_puzzle(string s, vector<int> c)
{
	n = s.size();

	string ans = s;

	int k = c.size();

	for(int i = 0; i < n ; i++) v[i + 1] = s[i];

	for(int i = 1; i <= k; i++) sz[i] = c[i - 1];

	ini[1] = 1, fim[k] = n - sz[k] + 1;

	for(int i = 2; i <= k; i++) ini[i] = ini[i - 1] + sz[i - 1] + 1;

	for(int i = k - 1; i >= 1; i--) fim[i] = fim[i + 1] - sz[i] - 1;

	for(int i = 1; i <= k; i++)
	{
		memset(cnt, 0, sizeof cnt);

		for(int p = ini[i]; p <= fim[i]; p++)
			for(int j = p; j < p + sz[i]; j++) global[j] ++, cnt[j] ++;

		for(int j = 1; j <= n; j++) if(cnt[j] == fim[i] - ini[i] + 1) ans[j - 1] = 'X';
	}

	for(int i = 1; i <= n; i++)
	{
		if(!global[i] && ans[i - 1] != 'X') ans[i - 1] = '_';

		else if(ans[i - 1] == '.') ans[i - 1] = '?';
	}

	return ans;
}

Compilation message

paint.cpp: In function 'int g(char)':
paint.cpp:15:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1016 KB n = 13, m = 1
2 Correct 2 ms 1128 KB n = 18, m = 1
3 Correct 2 ms 1236 KB n = 17, m = 1
4 Correct 2 ms 1348 KB n = 1, m = 1
5 Correct 2 ms 1380 KB n = 20, m = 1
6 Correct 2 ms 1384 KB n = 20, m = 1
7 Correct 2 ms 1392 KB n = 20, m = 1

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1016 KB n = 13, m = 1
2 Correct 2 ms 1128 KB n = 18, m = 1
3 Correct 2 ms 1236 KB n = 17, m = 1
4 Correct 2 ms 1348 KB n = 1, m = 1
5 Correct 2 ms 1380 KB n = 20, m = 1
6 Correct 2 ms 1384 KB n = 20, m = 1
7 Correct 2 ms 1392 KB n = 20, m = 1
8 Correct 2 ms 1392 KB n = 20, m = 5
9 Correct 2 ms 1396 KB n = 18, m = 3
10 Correct 2 ms 1508 KB n = 17, m = 2
11 Correct 2 ms 1508 KB n = 20, m = 2
12 Correct 2 ms 1512 KB n = 17, m = 4
13 Correct 2 ms 1532 KB n = 17, m = 6
14 Correct 2 ms 1536 KB n = 17, m = 1
15 Correct 2 ms 1540 KB n = 17, m = 4
16 Correct 2 ms 1544 KB n = 13, m = 3
17 Correct 2 ms 1548 KB n = 18, m = 4
18 Correct 2 ms 1552 KB n = 20, m = 10
19 Correct 2 ms 1556 KB n = 19, m = 10

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1016 KB n = 13, m = 1
2 Correct 2 ms 1128 KB n = 18, m = 1
3 Correct 2 ms 1236 KB n = 17, m = 1
4 Correct 2 ms 1348 KB n = 1, m = 1
5 Correct 2 ms 1380 KB n = 20, m = 1
6 Correct 2 ms 1384 KB n = 20, m = 1
7 Correct 2 ms 1392 KB n = 20, m = 1
8 Correct 2 ms 1392 KB n = 20, m = 5
9 Correct 2 ms 1396 KB n = 18, m = 3
10 Correct 2 ms 1508 KB n = 17, m = 2
11 Correct 2 ms 1508 KB n = 20, m = 2
12 Correct 2 ms 1512 KB n = 17, m = 4
13 Correct 2 ms 1532 KB n = 17, m = 6
14 Correct 2 ms 1536 KB n = 17, m = 1
15 Correct 2 ms 1540 KB n = 17, m = 4
16 Correct 2 ms 1544 KB n = 13, m = 3
17 Correct 2 ms 1548 KB n = 18, m = 4
18 Correct 2 ms 1552 KB n = 20, m = 10
19 Correct 2 ms 1556 KB n = 19, m = 10
20 Correct 2 ms 1560 KB n = 100, m = 5
21 Correct 2 ms 1564 KB n = 90, m = 3
22 Correct 2 ms 1572 KB n = 86, m = 2
23 Correct 2 ms 1576 KB n = 81, m = 4
24 Correct 2 ms 1580 KB n = 89, m = 10
25 Correct 3 ms 1584 KB n = 81, m = 23
26 Correct 2 ms 1588 KB n = 86, m = 8
27 Correct 3 ms 1592 KB n = 53, m = 22
28 Correct 3 ms 1596 KB n = 89, m = 35
29 Correct 3 ms 1600 KB n = 63, m = 25
30 Correct 4 ms 1604 KB n = 100, m = 50
31 Correct 4 ms 1608 KB n = 99, m = 50

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1016 KB n = 13, m = 1
2 Correct 2 ms 1128 KB n = 18, m = 1
3 Correct 2 ms 1236 KB n = 17, m = 1
4 Correct 2 ms 1348 KB n = 1, m = 1
5 Correct 2 ms 1380 KB n = 20, m = 1
6 Correct 2 ms 1384 KB n = 20, m = 1
7 Correct 2 ms 1392 KB n = 20, m = 1
8 Correct 2 ms 1392 KB n = 20, m = 5
9 Correct 2 ms 1396 KB n = 18, m = 3
10 Correct 2 ms 1508 KB n = 17, m = 2
11 Correct 2 ms 1508 KB n = 20, m = 2
12 Correct 2 ms 1512 KB n = 17, m = 4
13 Correct 2 ms 1532 KB n = 17, m = 6
14 Correct 2 ms 1536 KB n = 17, m = 1
15 Correct 2 ms 1540 KB n = 17, m = 4
16 Correct 2 ms 1544 KB n = 13, m = 3
17 Correct 2 ms 1548 KB n = 18, m = 4
18 Correct 2 ms 1552 KB n = 20, m = 10
19 Correct 2 ms 1556 KB n = 19, m = 10
20 Correct 2 ms 1560 KB n = 100, m = 5
21 Correct 2 ms 1564 KB n = 90, m = 3
22 Correct 2 ms 1572 KB n = 86, m = 2
23 Correct 2 ms 1576 KB n = 81, m = 4
24 Correct 2 ms 1580 KB n = 89, m = 10
25 Correct 3 ms 1584 KB n = 81, m = 23
26 Correct 2 ms 1588 KB n = 86, m = 8
27 Correct 3 ms 1592 KB n = 53, m = 22
28 Correct 3 ms 1596 KB n = 89, m = 35
29 Correct 3 ms 1600 KB n = 63, m = 25
30 Correct 4 ms 1604 KB n = 100, m = 50
31 Correct 4 ms 1608 KB n = 99, m = 50
32 Incorrect 2 ms 1608 KB char #1 differ - expected: 'X', found: '?'
33 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1016 KB n = 13, m = 1
2 Correct 2 ms 1128 KB n = 18, m = 1
3 Correct 2 ms 1236 KB n = 17, m = 1
4 Correct 2 ms 1348 KB n = 1, m = 1
5 Correct 2 ms 1380 KB n = 20, m = 1
6 Correct 2 ms 1384 KB n = 20, m = 1
7 Correct 2 ms 1392 KB n = 20, m = 1
8 Correct 2 ms 1392 KB n = 20, m = 5
9 Correct 2 ms 1396 KB n = 18, m = 3
10 Correct 2 ms 1508 KB n = 17, m = 2
11 Correct 2 ms 1508 KB n = 20, m = 2
12 Correct 2 ms 1512 KB n = 17, m = 4
13 Correct 2 ms 1532 KB n = 17, m = 6
14 Correct 2 ms 1536 KB n = 17, m = 1
15 Correct 2 ms 1540 KB n = 17, m = 4
16 Correct 2 ms 1544 KB n = 13, m = 3
17 Correct 2 ms 1548 KB n = 18, m = 4
18 Correct 2 ms 1552 KB n = 20, m = 10
19 Correct 2 ms 1556 KB n = 19, m = 10
20 Correct 2 ms 1560 KB n = 100, m = 5
21 Correct 2 ms 1564 KB n = 90, m = 3
22 Correct 2 ms 1572 KB n = 86, m = 2
23 Correct 2 ms 1576 KB n = 81, m = 4
24 Correct 2 ms 1580 KB n = 89, m = 10
25 Correct 3 ms 1584 KB n = 81, m = 23
26 Correct 2 ms 1588 KB n = 86, m = 8
27 Correct 3 ms 1592 KB n = 53, m = 22
28 Correct 3 ms 1596 KB n = 89, m = 35
29 Correct 3 ms 1600 KB n = 63, m = 25
30 Correct 4 ms 1604 KB n = 100, m = 50
31 Correct 4 ms 1608 KB n = 99, m = 50
32 Incorrect 2 ms 1608 KB char #1 differ - expected: 'X', found: '?'
33 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1016 KB n = 13, m = 1
2 Correct 2 ms 1128 KB n = 18, m = 1
3 Correct 2 ms 1236 KB n = 17, m = 1
4 Correct 2 ms 1348 KB n = 1, m = 1
5 Correct 2 ms 1380 KB n = 20, m = 1
6 Correct 2 ms 1384 KB n = 20, m = 1
7 Correct 2 ms 1392 KB n = 20, m = 1
8 Correct 2 ms 1392 KB n = 20, m = 5
9 Correct 2 ms 1396 KB n = 18, m = 3
10 Correct 2 ms 1508 KB n = 17, m = 2
11 Correct 2 ms 1508 KB n = 20, m = 2
12 Correct 2 ms 1512 KB n = 17, m = 4
13 Correct 2 ms 1532 KB n = 17, m = 6
14 Correct 2 ms 1536 KB n = 17, m = 1
15 Correct 2 ms 1540 KB n = 17, m = 4
16 Correct 2 ms 1544 KB n = 13, m = 3
17 Correct 2 ms 1548 KB n = 18, m = 4
18 Correct 2 ms 1552 KB n = 20, m = 10
19 Correct 2 ms 1556 KB n = 19, m = 10
20 Correct 2 ms 1560 KB n = 100, m = 5
21 Correct 2 ms 1564 KB n = 90, m = 3
22 Correct 2 ms 1572 KB n = 86, m = 2
23 Correct 2 ms 1576 KB n = 81, m = 4
24 Correct 2 ms 1580 KB n = 89, m = 10
25 Correct 3 ms 1584 KB n = 81, m = 23
26 Correct 2 ms 1588 KB n = 86, m = 8
27 Correct 3 ms 1592 KB n = 53, m = 22
28 Correct 3 ms 1596 KB n = 89, m = 35
29 Correct 3 ms 1600 KB n = 63, m = 25
30 Correct 4 ms 1604 KB n = 100, m = 50
31 Correct 4 ms 1608 KB n = 99, m = 50
32 Incorrect 2 ms 1608 KB char #1 differ - expected: 'X', found: '?'
33 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1016 KB n = 13, m = 1
2 Correct 2 ms 1128 KB n = 18, m = 1
3 Correct 2 ms 1236 KB n = 17, m = 1
4 Correct 2 ms 1348 KB n = 1, m = 1
5 Correct 2 ms 1380 KB n = 20, m = 1
6 Correct 2 ms 1384 KB n = 20, m = 1
7 Correct 2 ms 1392 KB n = 20, m = 1
8 Correct 2 ms 1392 KB n = 20, m = 5
9 Correct 2 ms 1396 KB n = 18, m = 3
10 Correct 2 ms 1508 KB n = 17, m = 2
11 Correct 2 ms 1508 KB n = 20, m = 2
12 Correct 2 ms 1512 KB n = 17, m = 4
13 Correct 2 ms 1532 KB n = 17, m = 6
14 Correct 2 ms 1536 KB n = 17, m = 1
15 Correct 2 ms 1540 KB n = 17, m = 4
16 Correct 2 ms 1544 KB n = 13, m = 3
17 Correct 2 ms 1548 KB n = 18, m = 4
18 Correct 2 ms 1552 KB n = 20, m = 10
19 Correct 2 ms 1556 KB n = 19, m = 10
20 Correct 2 ms 1560 KB n = 100, m = 5
21 Correct 2 ms 1564 KB n = 90, m = 3
22 Correct 2 ms 1572 KB n = 86, m = 2
23 Correct 2 ms 1576 KB n = 81, m = 4
24 Correct 2 ms 1580 KB n = 89, m = 10
25 Correct 3 ms 1584 KB n = 81, m = 23
26 Correct 2 ms 1588 KB n = 86, m = 8
27 Correct 3 ms 1592 KB n = 53, m = 22
28 Correct 3 ms 1596 KB n = 89, m = 35
29 Correct 3 ms 1600 KB n = 63, m = 25
30 Correct 4 ms 1604 KB n = 100, m = 50
31 Correct 4 ms 1608 KB n = 99, m = 50
32 Incorrect 2 ms 1608 KB char #1 differ - expected: 'X', found: '?'
33 Halted 0 ms 0 KB -