oj.uz

Submission #958001

# Submission time Handle Problem Language Result Execution time Memory
958001 2024-04-04T15:51:08 Z Lalic Paint By Numbers (IOI16_paint) C++17
80 / 100
 2000 ms 3484 KB 
#include "paint.h"
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()
#define mp make_pair

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 2e5+10;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;

int memo[2][MAXN];

int is_pos(string s, vector<int>& c){
	int n=(int)s.size(), k=(int)c.size();
	vector<vector<int>> dp(n+1, vector<int>(k+1, 0));
	
	bool ok=0;
	int lastW=-1;
	for(int i=0;i<n;i++){
		if(s[i]=='_') lastW=i;
		
		if(i && s[i]!='X'){
			for(int j=0;j<=k;j++)
				dp[i][j]=dp[i-1][j];
		}
		else if(s[i]=='X') ok=1;
		
		if(ok) dp[i][0]=0;
		else dp[i][0]=1;
		
		for(int j=1;j<=k;j++){
			if(i+1<c[j-1] || i-lastW<c[j-1] || (i-c[j-1]>=0 && s[i-c[j-1]]=='X') || (i<n-1 && s[i+1]=='X')) continue;
			if(i-c[j-1]-1<0){
				if(j==1) dp[i][j]=i+1;
				else dp[i][j]=0;
			}
			else if(dp[i-c[j-1]-1][j-1]) dp[i][j]=i+1;
		}
	}
	
	if(dp[n-1][k]){
		int ptr=n-1, qnt=k;
		while(qnt){
			int aux=dp[ptr][qnt];
			
			while(ptr>=aux){
				memo[0][ptr]=1;
				ptr--;
			}
			for(int i=0;i<c[qnt-1];i++){
				memo[1][ptr]=1;
				ptr--;
			}
			if(ptr>=0) memo[0][ptr]=1;
			ptr--;
			
			qnt--;
		}
	}
	
	return dp[n-1][k];
}

string solve_puzzle(string s, vector<int> c) {
    string ans="";
    memset(memo, 0, sizeof memo);
    
    for(int i=0;i<(int)s.size();i++){
		if(s[i]!='.') ans+=s[i];
		else{
			s[i]='X';
			int bl;
			if(memo[1][i]) bl=1;
			else bl=is_pos(s, c);
			
			s[i]='_';
			int wh;
			if(memo[0][i]) wh=1;
			else wh=is_pos(s, c);

			if(bl && wh) ans+='?';
			else if(bl) ans+='X';
			else ans+='_';
			
			s[i]='.';
		}
	}
		
	return ans;
}

Subtask #1
7.0 / 7.0

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

Subtask #2
3.0 / 3.0

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

Subtask #3
22.0 / 22.0

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

Subtask #4
27.0 / 27.0

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

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1880 KB n = 13, m = 1
2 Correct 1 ms 1884 KB n = 18, m = 1
3 Correct 1 ms 1884 KB n = 17, m = 1
4 Correct 1 ms 1884 KB n = 1, m = 1
5 Correct 1 ms 1884 KB n = 20, m = 1
6 Correct 1 ms 1884 KB n = 20, m = 1
7 Correct 1 ms 1884 KB n = 20, m = 1
8 Correct 1 ms 1884 KB n = 20, m = 5
9 Correct 1 ms 1880 KB n = 18, m = 3
10 Correct 1 ms 1884 KB n = 17, m = 2
11 Correct 1 ms 1884 KB n = 20, m = 2
12 Correct 1 ms 1884 KB n = 17, m = 4
13 Correct 1 ms 1884 KB n = 17, m = 6
14 Correct 1 ms 1884 KB n = 17, m = 1
15 Correct 1 ms 1884 KB n = 17, m = 4
16 Correct 1 ms 1884 KB n = 13, m = 3
17 Correct 1 ms 1884 KB n = 18, m = 4
18 Correct 1 ms 1884 KB n = 20, m = 10
19 Correct 1 ms 1884 KB n = 19, m = 10
20 Correct 1 ms 1884 KB n = 100, m = 5
21 Correct 1 ms 1880 KB n = 90, m = 3
22 Correct 1 ms 1884 KB n = 86, m = 2
23 Correct 1 ms 1884 KB n = 81, m = 4
24 Correct 1 ms 1884 KB n = 89, m = 10
25 Correct 2 ms 1884 KB n = 81, m = 23
26 Correct 1 ms 1884 KB n = 86, m = 8
27 Correct 1 ms 1884 KB n = 53, m = 22
28 Correct 2 ms 2024 KB n = 89, m = 35
29 Correct 1 ms 1880 KB n = 63, m = 25
30 Correct 2 ms 1884 KB n = 100, m = 50
31 Correct 3 ms 1824 KB n = 99, m = 50
32 Correct 1 ms 1884 KB n = 13, m = 4
33 Correct 1 ms 1884 KB n = 86, m = 2
34 Correct 1 ms 1884 KB n = 88, m = 2
35 Correct 1 ms 1884 KB n = 86, m = 2
36 Correct 1 ms 1884 KB n = 81, m = 6
37 Correct 1 ms 1884 KB n = 98, m = 7
38 Correct 1 ms 1884 KB n = 92, m = 7
39 Correct 1 ms 1884 KB n = 88, m = 21
40 Correct 1 ms 1884 KB n = 90, m = 21
41 Correct 2 ms 1884 KB n = 98, m = 22
42 Correct 1 ms 1880 KB n = 11, m = 2
43 Correct 2 ms 1884 KB n = 11, m = 2
44 Correct 1 ms 1884 KB n = 13, m = 3
45 Correct 1 ms 1884 KB n = 86, m = 2
46 Correct 1 ms 1880 KB n = 81, m = 2
47 Correct 1 ms 1884 KB n = 93, m = 2
48 Correct 1 ms 1884 KB n = 81, m = 2
49 Correct 1 ms 1884 KB n = 86, m = 2
50 Correct 1 ms 1884 KB n = 90, m = 2
51 Correct 1 ms 1884 KB n = 87, m = 2
52 Correct 1 ms 1884 KB n = 97, m = 2
53 Correct 1 ms 1884 KB n = 85, m = 2
54 Correct 1 ms 1884 KB n = 88, m = 7
55 Correct 1 ms 1884 KB n = 96, m = 7
56 Correct 1 ms 1884 KB n = 85, m = 7
57 Correct 1 ms 1884 KB n = 92, m = 7
58 Correct 1 ms 1884 KB n = 92, m = 7
59 Correct 1 ms 1884 KB n = 86, m = 7
60 Correct 1 ms 1884 KB n = 87, m = 7
61 Correct 1 ms 1884 KB n = 100, m = 7
62 Correct 2 ms 1884 KB n = 100, m = 7
63 Correct 1 ms 1884 KB n = 92, m = 21
64 Correct 1 ms 1912 KB n = 93, m = 22
65 Correct 2 ms 1884 KB n = 95, m = 22
66 Correct 1 ms 1884 KB n = 98, m = 22
67 Correct 1 ms 1768 KB n = 94, m = 22
68 Correct 1 ms 1880 KB n = 93, m = 22
69 Correct 1 ms 1884 KB n = 88, m = 21
70 Correct 1 ms 1884 KB n = 83, m = 20
71 Correct 1 ms 1884 KB n = 99, m = 23
72 Correct 1 ms 1884 KB n = 96, m = 19

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1880 KB n = 13, m = 1
2 Correct 1 ms 1884 KB n = 18, m = 1
3 Correct 1 ms 1884 KB n = 17, m = 1
4 Correct 1 ms 1884 KB n = 1, m = 1
5 Correct 1 ms 1884 KB n = 20, m = 1
6 Correct 1 ms 1884 KB n = 20, m = 1
7 Correct 1 ms 1884 KB n = 20, m = 1
8 Correct 1 ms 1884 KB n = 20, m = 5
9 Correct 1 ms 1880 KB n = 18, m = 3
10 Correct 1 ms 1884 KB n = 17, m = 2
11 Correct 1 ms 1884 KB n = 20, m = 2
12 Correct 1 ms 1884 KB n = 17, m = 4
13 Correct 1 ms 1884 KB n = 17, m = 6
14 Correct 1 ms 1884 KB n = 17, m = 1
15 Correct 1 ms 1884 KB n = 17, m = 4
16 Correct 1 ms 1884 KB n = 13, m = 3
17 Correct 1 ms 1884 KB n = 18, m = 4
18 Correct 1 ms 1884 KB n = 20, m = 10
19 Correct 1 ms 1884 KB n = 19, m = 10
20 Correct 1 ms 1884 KB n = 100, m = 5
21 Correct 1 ms 1880 KB n = 90, m = 3
22 Correct 1 ms 1884 KB n = 86, m = 2
23 Correct 1 ms 1884 KB n = 81, m = 4
24 Correct 1 ms 1884 KB n = 89, m = 10
25 Correct 2 ms 1884 KB n = 81, m = 23
26 Correct 1 ms 1884 KB n = 86, m = 8
27 Correct 1 ms 1884 KB n = 53, m = 22
28 Correct 2 ms 2024 KB n = 89, m = 35
29 Correct 1 ms 1880 KB n = 63, m = 25
30 Correct 2 ms 1884 KB n = 100, m = 50
31 Correct 3 ms 1824 KB n = 99, m = 50
32 Correct 1 ms 1884 KB n = 13, m = 4
33 Correct 1 ms 1884 KB n = 86, m = 2
34 Correct 1 ms 1884 KB n = 88, m = 2
35 Correct 1 ms 1884 KB n = 86, m = 2
36 Correct 1 ms 1884 KB n = 81, m = 6
37 Correct 1 ms 1884 KB n = 98, m = 7
38 Correct 1 ms 1884 KB n = 92, m = 7
39 Correct 1 ms 1884 KB n = 88, m = 21
40 Correct 1 ms 1884 KB n = 90, m = 21
41 Correct 2 ms 1884 KB n = 98, m = 22
42 Correct 1 ms 1880 KB n = 11, m = 2
43 Correct 2 ms 1884 KB n = 11, m = 2
44 Correct 1 ms 1884 KB n = 13, m = 3
45 Correct 1 ms 1884 KB n = 86, m = 2
46 Correct 1 ms 1880 KB n = 81, m = 2
47 Correct 1 ms 1884 KB n = 93, m = 2
48 Correct 1 ms 1884 KB n = 81, m = 2
49 Correct 1 ms 1884 KB n = 86, m = 2
50 Correct 1 ms 1884 KB n = 90, m = 2
51 Correct 1 ms 1884 KB n = 87, m = 2
52 Correct 1 ms 1884 KB n = 97, m = 2
53 Correct 1 ms 1884 KB n = 85, m = 2
54 Correct 1 ms 1884 KB n = 88, m = 7
55 Correct 1 ms 1884 KB n = 96, m = 7
56 Correct 1 ms 1884 KB n = 85, m = 7
57 Correct 1 ms 1884 KB n = 92, m = 7
58 Correct 1 ms 1884 KB n = 92, m = 7
59 Correct 1 ms 1884 KB n = 86, m = 7
60 Correct 1 ms 1884 KB n = 87, m = 7
61 Correct 1 ms 1884 KB n = 100, m = 7
62 Correct 2 ms 1884 KB n = 100, m = 7
63 Correct 1 ms 1884 KB n = 92, m = 21
64 Correct 1 ms 1912 KB n = 93, m = 22
65 Correct 2 ms 1884 KB n = 95, m = 22
66 Correct 1 ms 1884 KB n = 98, m = 22
67 Correct 1 ms 1768 KB n = 94, m = 22
68 Correct 1 ms 1880 KB n = 93, m = 22
69 Correct 1 ms 1884 KB n = 88, m = 21
70 Correct 1 ms 1884 KB n = 83, m = 20
71 Correct 1 ms 1884 KB n = 99, m = 23
72 Correct 1 ms 1884 KB n = 96, m = 19
73 Correct 746 ms 2340 KB n = 4825, m = 5
74 Correct 765 ms 2308 KB n = 4384, m = 5
75 Correct 872 ms 2356 KB n = 4528, m = 5
76 Correct 934 ms 2416 KB n = 4980, m = 5
77 Correct 1022 ms 2648 KB n = 4730, m = 5
78 Correct 1074 ms 2516 KB n = 4784, m = 5
79 Correct 1000 ms 2532 KB n = 4875, m = 5
80 Correct 948 ms 2384 KB n = 4576, m = 5
81 Correct 493 ms 2376 KB n = 4297, m = 5
82 Execution timed out 2064 ms 3484 KB Time limit exceeded
83 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1880 KB n = 13, m = 1
2 Correct 1 ms 1884 KB n = 18, m = 1
3 Correct 1 ms 1884 KB n = 17, m = 1
4 Correct 1 ms 1884 KB n = 1, m = 1
5 Correct 1 ms 1884 KB n = 20, m = 1
6 Correct 1 ms 1884 KB n = 20, m = 1
7 Correct 1 ms 1884 KB n = 20, m = 1
8 Correct 1 ms 1884 KB n = 20, m = 5
9 Correct 1 ms 1880 KB n = 18, m = 3
10 Correct 1 ms 1884 KB n = 17, m = 2
11 Correct 1 ms 1884 KB n = 20, m = 2
12 Correct 1 ms 1884 KB n = 17, m = 4
13 Correct 1 ms 1884 KB n = 17, m = 6
14 Correct 1 ms 1884 KB n = 17, m = 1
15 Correct 1 ms 1884 KB n = 17, m = 4
16 Correct 1 ms 1884 KB n = 13, m = 3
17 Correct 1 ms 1884 KB n = 18, m = 4
18 Correct 1 ms 1884 KB n = 20, m = 10
19 Correct 1 ms 1884 KB n = 19, m = 10
20 Correct 1 ms 1884 KB n = 100, m = 5
21 Correct 1 ms 1880 KB n = 90, m = 3
22 Correct 1 ms 1884 KB n = 86, m = 2
23 Correct 1 ms 1884 KB n = 81, m = 4
24 Correct 1 ms 1884 KB n = 89, m = 10
25 Correct 2 ms 1884 KB n = 81, m = 23
26 Correct 1 ms 1884 KB n = 86, m = 8
27 Correct 1 ms 1884 KB n = 53, m = 22
28 Correct 2 ms 2024 KB n = 89, m = 35
29 Correct 1 ms 1880 KB n = 63, m = 25
30 Correct 2 ms 1884 KB n = 100, m = 50
31 Correct 3 ms 1824 KB n = 99, m = 50
32 Correct 1 ms 1884 KB n = 13, m = 4
33 Correct 1 ms 1884 KB n = 86, m = 2
34 Correct 1 ms 1884 KB n = 88, m = 2
35 Correct 1 ms 1884 KB n = 86, m = 2
36 Correct 1 ms 1884 KB n = 81, m = 6
37 Correct 1 ms 1884 KB n = 98, m = 7
38 Correct 1 ms 1884 KB n = 92, m = 7
39 Correct 1 ms 1884 KB n = 88, m = 21
40 Correct 1 ms 1884 KB n = 90, m = 21
41 Correct 2 ms 1884 KB n = 98, m = 22
42 Correct 1 ms 1880 KB n = 11, m = 2
43 Correct 2 ms 1884 KB n = 11, m = 2
44 Correct 1 ms 1884 KB n = 13, m = 3
45 Correct 1 ms 1884 KB n = 86, m = 2
46 Correct 1 ms 1880 KB n = 81, m = 2
47 Correct 1 ms 1884 KB n = 93, m = 2
48 Correct 1 ms 1884 KB n = 81, m = 2
49 Correct 1 ms 1884 KB n = 86, m = 2
50 Correct 1 ms 1884 KB n = 90, m = 2
51 Correct 1 ms 1884 KB n = 87, m = 2
52 Correct 1 ms 1884 KB n = 97, m = 2
53 Correct 1 ms 1884 KB n = 85, m = 2
54 Correct 1 ms 1884 KB n = 88, m = 7
55 Correct 1 ms 1884 KB n = 96, m = 7
56 Correct 1 ms 1884 KB n = 85, m = 7
57 Correct 1 ms 1884 KB n = 92, m = 7
58 Correct 1 ms 1884 KB n = 92, m = 7
59 Correct 1 ms 1884 KB n = 86, m = 7
60 Correct 1 ms 1884 KB n = 87, m = 7
61 Correct 1 ms 1884 KB n = 100, m = 7
62 Correct 2 ms 1884 KB n = 100, m = 7
63 Correct 1 ms 1884 KB n = 92, m = 21
64 Correct 1 ms 1912 KB n = 93, m = 22
65 Correct 2 ms 1884 KB n = 95, m = 22
66 Correct 1 ms 1884 KB n = 98, m = 22
67 Correct 1 ms 1768 KB n = 94, m = 22
68 Correct 1 ms 1880 KB n = 93, m = 22
69 Correct 1 ms 1884 KB n = 88, m = 21
70 Correct 1 ms 1884 KB n = 83, m = 20
71 Correct 1 ms 1884 KB n = 99, m = 23
72 Correct 1 ms 1884 KB n = 96, m = 19
73 Correct 746 ms 2340 KB n = 4825, m = 5
74 Correct 765 ms 2308 KB n = 4384, m = 5
75 Correct 872 ms 2356 KB n = 4528, m = 5
76 Correct 934 ms 2416 KB n = 4980, m = 5
77 Correct 1022 ms 2648 KB n = 4730, m = 5
78 Correct 1074 ms 2516 KB n = 4784, m = 5
79 Correct 1000 ms 2532 KB n = 4875, m = 5
80 Correct 948 ms 2384 KB n = 4576, m = 5
81 Correct 493 ms 2376 KB n = 4297, m = 5
82 Execution timed out 2064 ms 3484 KB Time limit exceeded
83 Halted 0 ms 0 KB -