oj.uz

Submission #138888

# Submission time Handle Problem Language Result Execution time Memory
138888 2019-07-30T18:42:02 Z bogdan10bos Paint By Numbers (IOI16_paint) C++14
32 / 100
 3 ms 380 KB 
/// Prosta
#include "paint.h"
#include <bits/stdc++.h>

using namespace std;

int N, K;

vector<int> sum[2];

int getsum(int id, int st, int dr)
{
	if(st > dr)	return 0;
	if(st < 0)	return 0;
	if(st == 0)	return sum[id][dr];
	return sum[id][dr] - sum[id][st - 1];
}

void makesum(string s)
{
	sum[0].resize(N);
	sum[1].resize(N);
	for(int i = 0; i < N; i++)
	{
		if(i > 0)
		{
			sum[0][i] = sum[0][i - 1];
			sum[1][i] = sum[1][i - 1];
		}
		if(s[i] == '_')	sum[0][i]++;
		if(s[i] == 'X')	sum[1][i]++;
	}
}

void solve(string s, vector<int> c, vector< vector<int> > &can)
{
	makesum(s);
	can.resize(N);

	auto getcan = [&](int x, int y)
		{
		if(y >= 0 && x >= 0)	return can[x][y];
		if(y == 0)return 1;
		if(y > 0)	return 0;
		return 0;
		};

	for(int i = 0; i < N; i++)
	{
		can[i].resize(K + 1);
		can[i][0] = getsum(1, 0, i) == 0;
		for(int j = 1; j <= K; j++)
		{
			int l = c[j - 1];
			can[i][j] = 0;
			if(s[i] == '_')
				can[i][j] |= (i > 0 ? can[i - 1][j] : 0);
			else if(s[i] == 'X')
				can[i][j] |= ( (i >= l - 1 && getsum(0, i - l + 1, i) == 0 && getsum(1, i - l, i - l) == 0) ? getcan(i - l - 1, j - 1) : 0);
			else
			{
				can[i][j] |= (i > 0 ? can[i - 1][j] : 0);
				can[i][j] |= ( (i >= l - 1 && getsum(0, i - l + 1, i) == 0 && getsum(1, i - l, i - l) == 0) ? getcan(i - l - 1, j - 1) : 0);
			}
		}
	}
}

string solve_puzzle(string s, vector<int> c)
{
    N = s.size(), K = c.size();
    vector< vector<int> > pfx, sfx;
    solve(s, c, pfx);

    reverse(begin(s), end(s));
    reverse(begin(c), end(c));
    solve(s, c, sfx);

    reverse(begin(s), end(s));
    reverse(begin(c), end(c));

    makesum(s);
    string sol = "";

    vector<int> blk(N + 2), wht(N + 2);

    for(int i = 0; i < N; i++)
    {
    	bool white = false;
    	for(int j = 0; j <= K; j++)
    	{
    		bool left = false;
    		if(i == 0)	left = (j == 0 ? 1 : 0);
    		else	left = pfx[i - 1][j];

    		bool right = false;
    		if(i == N - 1)	right = (j == K ? 1 : 0);
    		else	right = sfx[N - i - 2][K - j];

    		if(left && right)
    		{
    			white = true;
    			break;
    		}
    	}
    	wht[i] = white;

    	for(int j = 0; j < K; j++)
    	{
    		if(i + c[j] > N)	continue;
    		bool left = false;
    		if(i == 0)	left = (j == 0 ? 1 : 0);
    		else if(i == 1)	left = (j == 0 ? pfx[i - 1][0] : 0);
    		else	left = (pfx[i - 2][j] & (s[i - 1] != 'X'));

    		i += c[j] - 1;
    		j++;
    		bool right = false;
    		if(i == N - 1)	right = (j == K ? 1 : 0);
    		else if(i == N - 2) right = (j == K ? sfx[N - i - 2][0] : 0);
    		else	right = (sfx[N - i - 3][K - j] & (s[i + 1] != 'X'));
    		j--;
    		i -= c[j] - 1;

    		if(!left || !right)	continue;
    		if(getsum(0, i, i + c[j] - 1) > 0)	continue;

    		blk[i]++;
    		blk[i + c[j]]--;
    	}
    }

    for(int i = 0; i < N; i++)
    {
    	if(i > 0)	blk[i] += blk[i - 1];
    	if(s[i] != '.')
    		sol.push_back(s[i]);
    	else if(wht[i] && blk[i] > 0)
    		sol.push_back('?');
    	else if(wht[i])
    		sol.push_back('_');
    	else
    		sol.push_back('X');
    }

    return sol;
}

Subtask #1
7.0 / 7.0

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

Subtask #2
3.0 / 3.0

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

Subtask #3
22.0 / 22.0

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

Subtask #4
0 / 27.0

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

Subtask #5
0 / 21.0

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

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

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