# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
961321 | 2024-04-11T20:05:19 Z | Ahmed57 | Paint By Numbers (IOI16_paint) | C++17 | 1 ms | 2396 KB |
#include <bits/stdc++.h> #include "paint.h" using namespace std; int pref[100001][101]; int suf[100001][101]; string solve_puzzle(string s, vector<int> c){ int n = s.size() , k = c.size(); pref[0][0] = 1; suf[n+1][k] = 1; suf[n+2][k] = 1; s = '0'+s; int wi[n+1] = {0},bl[n+1] = {0}; int nah[n+1] = {0},part[n+2] = {0}; for(int i = 1;i<=s.size();i++){ wi[i] = wi[i-1]; bl[i] = bl[i-1]; if(s[i]=='_'){ wi[i] = wi[i-1]+1; }else if(s[i]=='X'){ bl[i] = bl[i-1]+1; } } for(int i = 1;i<=n;i++){ for(int j = 0;j<=k;j++){ if(s[i]=='.'||s[i]=='_'){ pref[i][j] |= pref[i-1][j]; }if(j>=1&&c[j-1]<=i&&wi[i]-wi[i-c[j-1]]==0&&(i-c[j-1]<=0||s[i-c[j-1]]!='X')){ //cout<<i<<"hhh "<<j<<endl; if(i-c[j-1]==0){ if(j==1)pref[i][j] |= 1; } else pref[i][j] |= pref[i-c[j-1]-1][j-1]; } } } for(int i = n;i>=1;i--){ for(int j = 0;j<=k;j++){ if(s[i]=='.'||s[i]=='_'){ suf[i][j] |= suf[i+1][j]; }if(j<k&&c[j]<=(n-i+1)&&wi[i+c[j]-1]-wi[i-1]==0&&(i+c[j]>n||s[i+c[j]]!='X')){ if(i+c[j]==n+1){ if(j==k-1)suf[i][j] = 1; } else suf[i][j] |= suf[i+c[j]+1][j+1]; } } } //cout<<pref[3][1]<<endl; for(int i = 1;i<=n;i++){ bool ss = 0; for(int j = 0;j<=k;j++){ if(pref[i-1][j]&&suf[i+1][j]&&s[i]!='X'){ ss = 1; } } if(ss)nah[i]|=1; } for(int i = 1;i<=n;i++){ for(int j = 0;j<k;j++){ if((i==1?(j==0):(pref[i-2][j]&&s[i-1]!='X'))&&i+c[j]-1<=n&&suf[i+c[j]+1][j+1]&&wi[i+c[j]-1]-wi[i-1]==0&&(i+c[j]>n||s[i+c[j]]!='X')){ if(i+c[j]>n){ if(j+1==k){ part[i]++; part[i+c[j]]--; } }else{ part[i]++; part[i+c[j]]--; } } } } for(int i = 1;i<=n;i++){ part[i]+=part[i-1]; if(part[i])nah[i]|=2; } string ans; for(int i = 1;i<=n;i++){ //cout<<nah[i]<<" "; if(nah[i]==3)ans+='?'; if(nah[i]==1)ans+='_'; if(nah[i]==2)ans+='X'; } return ans; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2392 KB | n = 13, m = 1 |
2 | Correct | 1 ms | 2396 KB | n = 18, m = 1 |
3 | Correct | 0 ms | 2396 KB | n = 17, m = 1 |
4 | Correct | 1 ms | 2396 KB | n = 1, m = 1 |
5 | Correct | 1 ms | 2396 KB | n = 20, m = 1 |
6 | Correct | 0 ms | 2396 KB | n = 20, m = 1 |
7 | Correct | 1 ms | 2396 KB | n = 20, m = 1 |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2392 KB | n = 13, m = 1 |
2 | Correct | 1 ms | 2396 KB | n = 18, m = 1 |
3 | Correct | 0 ms | 2396 KB | n = 17, m = 1 |
4 | Correct | 1 ms | 2396 KB | n = 1, m = 1 |
5 | Correct | 1 ms | 2396 KB | n = 20, m = 1 |
6 | Correct | 0 ms | 2396 KB | n = 20, m = 1 |
7 | Correct | 1 ms | 2396 KB | n = 20, m = 1 |
8 | Correct | 1 ms | 2396 KB | n = 20, m = 5 |
9 | Correct | 0 ms | 2396 KB | n = 18, m = 3 |
10 | Correct | 1 ms | 2396 KB | n = 17, m = 2 |
11 | Correct | 0 ms | 2396 KB | n = 20, m = 2 |
12 | Correct | 1 ms | 2396 KB | n = 17, m = 4 |
13 | Correct | 0 ms | 2396 KB | n = 17, m = 6 |
14 | Correct | 1 ms | 2396 KB | n = 17, m = 1 |
15 | Correct | 1 ms | 2392 KB | n = 17, m = 4 |
16 | Correct | 1 ms | 2396 KB | n = 13, m = 3 |
17 | Correct | 1 ms | 2396 KB | n = 18, m = 4 |
18 | Correct | 1 ms | 2396 KB | n = 20, m = 10 |
19 | Correct | 1 ms | 2396 KB | n = 19, m = 10 |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2392 KB | n = 13, m = 1 |
2 | Correct | 1 ms | 2396 KB | n = 18, m = 1 |
3 | Correct | 0 ms | 2396 KB | n = 17, m = 1 |
4 | Correct | 1 ms | 2396 KB | n = 1, m = 1 |
5 | Correct | 1 ms | 2396 KB | n = 20, m = 1 |
6 | Correct | 0 ms | 2396 KB | n = 20, m = 1 |
7 | Correct | 1 ms | 2396 KB | n = 20, m = 1 |
8 | Correct | 1 ms | 2396 KB | n = 20, m = 5 |
9 | Correct | 0 ms | 2396 KB | n = 18, m = 3 |
10 | Correct | 1 ms | 2396 KB | n = 17, m = 2 |
11 | Correct | 0 ms | 2396 KB | n = 20, m = 2 |
12 | Correct | 1 ms | 2396 KB | n = 17, m = 4 |
13 | Correct | 0 ms | 2396 KB | n = 17, m = 6 |
14 | Correct | 1 ms | 2396 KB | n = 17, m = 1 |
15 | Correct | 1 ms | 2392 KB | n = 17, m = 4 |
16 | Correct | 1 ms | 2396 KB | n = 13, m = 3 |
17 | Correct | 1 ms | 2396 KB | n = 18, m = 4 |
18 | Correct | 1 ms | 2396 KB | n = 20, m = 10 |
19 | Correct | 1 ms | 2396 KB | n = 19, m = 10 |
20 | Correct | 1 ms | 2392 KB | n = 100, m = 5 |
21 | Correct | 1 ms | 2396 KB | n = 90, m = 3 |
22 | Correct | 1 ms | 2396 KB | n = 86, m = 2 |
23 | Correct | 1 ms | 2396 KB | n = 81, m = 4 |
24 | Correct | 1 ms | 2392 KB | n = 89, m = 10 |
25 | Correct | 1 ms | 2396 KB | n = 81, m = 23 |
26 | Correct | 1 ms | 2396 KB | n = 86, m = 8 |
27 | Correct | 1 ms | 2396 KB | n = 53, m = 22 |
28 | Correct | 1 ms | 2396 KB | n = 89, m = 35 |
29 | Correct | 1 ms | 2396 KB | n = 63, m = 25 |
30 | Correct | 1 ms | 2396 KB | n = 100, m = 50 |
31 | Correct | 1 ms | 2396 KB | n = 99, m = 50 |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2392 KB | n = 13, m = 1 |
2 | Correct | 1 ms | 2396 KB | n = 18, m = 1 |
3 | Correct | 0 ms | 2396 KB | n = 17, m = 1 |
4 | Correct | 1 ms | 2396 KB | n = 1, m = 1 |
5 | Correct | 1 ms | 2396 KB | n = 20, m = 1 |
6 | Correct | 0 ms | 2396 KB | n = 20, m = 1 |
7 | Correct | 1 ms | 2396 KB | n = 20, m = 1 |
8 | Correct | 1 ms | 2396 KB | n = 20, m = 5 |
9 | Correct | 0 ms | 2396 KB | n = 18, m = 3 |
10 | Correct | 1 ms | 2396 KB | n = 17, m = 2 |
11 | Correct | 0 ms | 2396 KB | n = 20, m = 2 |
12 | Correct | 1 ms | 2396 KB | n = 17, m = 4 |
13 | Correct | 0 ms | 2396 KB | n = 17, m = 6 |
14 | Correct | 1 ms | 2396 KB | n = 17, m = 1 |
15 | Correct | 1 ms | 2392 KB | n = 17, m = 4 |
16 | Correct | 1 ms | 2396 KB | n = 13, m = 3 |
17 | Correct | 1 ms | 2396 KB | n = 18, m = 4 |
18 | Correct | 1 ms | 2396 KB | n = 20, m = 10 |
19 | Correct | 1 ms | 2396 KB | n = 19, m = 10 |
20 | Correct | 1 ms | 2392 KB | n = 100, m = 5 |
21 | Correct | 1 ms | 2396 KB | n = 90, m = 3 |
22 | Correct | 1 ms | 2396 KB | n = 86, m = 2 |
23 | Correct | 1 ms | 2396 KB | n = 81, m = 4 |
24 | Correct | 1 ms | 2392 KB | n = 89, m = 10 |
25 | Correct | 1 ms | 2396 KB | n = 81, m = 23 |
26 | Correct | 1 ms | 2396 KB | n = 86, m = 8 |
27 | Correct | 1 ms | 2396 KB | n = 53, m = 22 |
28 | Correct | 1 ms | 2396 KB | n = 89, m = 35 |
29 | Correct | 1 ms | 2396 KB | n = 63, m = 25 |
30 | Correct | 1 ms | 2396 KB | n = 100, m = 50 |
31 | Correct | 1 ms | 2396 KB | n = 99, m = 50 |
32 | Correct | 1 ms | 2392 KB | n = 13, m = 4 |
33 | Correct | 1 ms | 2396 KB | n = 86, m = 2 |
34 | Correct | 1 ms | 2396 KB | n = 88, m = 2 |
35 | Correct | 1 ms | 2396 KB | n = 86, m = 2 |
36 | Correct | 1 ms | 2396 KB | n = 81, m = 6 |
37 | Correct | 1 ms | 2392 KB | n = 98, m = 7 |
38 | Correct | 1 ms | 2392 KB | n = 92, m = 7 |
39 | Correct | 1 ms | 2396 KB | n = 88, m = 21 |
40 | Correct | 1 ms | 2396 KB | n = 90, m = 21 |
41 | Correct | 0 ms | 2396 KB | n = 98, m = 22 |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2392 KB | n = 13, m = 1 |
2 | Correct | 1 ms | 2396 KB | n = 18, m = 1 |
3 | Correct | 0 ms | 2396 KB | n = 17, m = 1 |
4 | Correct | 1 ms | 2396 KB | n = 1, m = 1 |
5 | Correct | 1 ms | 2396 KB | n = 20, m = 1 |
6 | Correct | 0 ms | 2396 KB | n = 20, m = 1 |
7 | Correct | 1 ms | 2396 KB | n = 20, m = 1 |
8 | Correct | 1 ms | 2396 KB | n = 20, m = 5 |
9 | Correct | 0 ms | 2396 KB | n = 18, m = 3 |
10 | Correct | 1 ms | 2396 KB | n = 17, m = 2 |
11 | Correct | 0 ms | 2396 KB | n = 20, m = 2 |
12 | Correct | 1 ms | 2396 KB | n = 17, m = 4 |
13 | Correct | 0 ms | 2396 KB | n = 17, m = 6 |
14 | Correct | 1 ms | 2396 KB | n = 17, m = 1 |
15 | Correct | 1 ms | 2392 KB | n = 17, m = 4 |
16 | Correct | 1 ms | 2396 KB | n = 13, m = 3 |
17 | Correct | 1 ms | 2396 KB | n = 18, m = 4 |
18 | Correct | 1 ms | 2396 KB | n = 20, m = 10 |
19 | Correct | 1 ms | 2396 KB | n = 19, m = 10 |
20 | Correct | 1 ms | 2392 KB | n = 100, m = 5 |
21 | Correct | 1 ms | 2396 KB | n = 90, m = 3 |
22 | Correct | 1 ms | 2396 KB | n = 86, m = 2 |
23 | Correct | 1 ms | 2396 KB | n = 81, m = 4 |
24 | Correct | 1 ms | 2392 KB | n = 89, m = 10 |
25 | Correct | 1 ms | 2396 KB | n = 81, m = 23 |
26 | Correct | 1 ms | 2396 KB | n = 86, m = 8 |
27 | Correct | 1 ms | 2396 KB | n = 53, m = 22 |
28 | Correct | 1 ms | 2396 KB | n = 89, m = 35 |
29 | Correct | 1 ms | 2396 KB | n = 63, m = 25 |
30 | Correct | 1 ms | 2396 KB | n = 100, m = 50 |
31 | Correct | 1 ms | 2396 KB | n = 99, m = 50 |
32 | Correct | 1 ms | 2392 KB | n = 13, m = 4 |
33 | Correct | 1 ms | 2396 KB | n = 86, m = 2 |
34 | Correct | 1 ms | 2396 KB | n = 88, m = 2 |
35 | Correct | 1 ms | 2396 KB | n = 86, m = 2 |
36 | Correct | 1 ms | 2396 KB | n = 81, m = 6 |
37 | Correct | 1 ms | 2392 KB | n = 98, m = 7 |
38 | Correct | 1 ms | 2392 KB | n = 92, m = 7 |
39 | Correct | 1 ms | 2396 KB | n = 88, m = 21 |
40 | Correct | 1 ms | 2396 KB | n = 90, m = 21 |
41 | Correct | 0 ms | 2396 KB | n = 98, m = 22 |
42 | Incorrect | 1 ms | 2396 KB | char #0 differ - expected: '?', found: '_' |
43 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2392 KB | n = 13, m = 1 |
2 | Correct | 1 ms | 2396 KB | n = 18, m = 1 |
3 | Correct | 0 ms | 2396 KB | n = 17, m = 1 |
4 | Correct | 1 ms | 2396 KB | n = 1, m = 1 |
5 | Correct | 1 ms | 2396 KB | n = 20, m = 1 |
6 | Correct | 0 ms | 2396 KB | n = 20, m = 1 |
7 | Correct | 1 ms | 2396 KB | n = 20, m = 1 |
8 | Correct | 1 ms | 2396 KB | n = 20, m = 5 |
9 | Correct | 0 ms | 2396 KB | n = 18, m = 3 |
10 | Correct | 1 ms | 2396 KB | n = 17, m = 2 |
11 | Correct | 0 ms | 2396 KB | n = 20, m = 2 |
12 | Correct | 1 ms | 2396 KB | n = 17, m = 4 |
13 | Correct | 0 ms | 2396 KB | n = 17, m = 6 |
14 | Correct | 1 ms | 2396 KB | n = 17, m = 1 |
15 | Correct | 1 ms | 2392 KB | n = 17, m = 4 |
16 | Correct | 1 ms | 2396 KB | n = 13, m = 3 |
17 | Correct | 1 ms | 2396 KB | n = 18, m = 4 |
18 | Correct | 1 ms | 2396 KB | n = 20, m = 10 |
19 | Correct | 1 ms | 2396 KB | n = 19, m = 10 |
20 | Correct | 1 ms | 2392 KB | n = 100, m = 5 |
21 | Correct | 1 ms | 2396 KB | n = 90, m = 3 |
22 | Correct | 1 ms | 2396 KB | n = 86, m = 2 |
23 | Correct | 1 ms | 2396 KB | n = 81, m = 4 |
24 | Correct | 1 ms | 2392 KB | n = 89, m = 10 |
25 | Correct | 1 ms | 2396 KB | n = 81, m = 23 |
26 | Correct | 1 ms | 2396 KB | n = 86, m = 8 |
27 | Correct | 1 ms | 2396 KB | n = 53, m = 22 |
28 | Correct | 1 ms | 2396 KB | n = 89, m = 35 |
29 | Correct | 1 ms | 2396 KB | n = 63, m = 25 |
30 | Correct | 1 ms | 2396 KB | n = 100, m = 50 |
31 | Correct | 1 ms | 2396 KB | n = 99, m = 50 |
32 | Correct | 1 ms | 2392 KB | n = 13, m = 4 |
33 | Correct | 1 ms | 2396 KB | n = 86, m = 2 |
34 | Correct | 1 ms | 2396 KB | n = 88, m = 2 |
35 | Correct | 1 ms | 2396 KB | n = 86, m = 2 |
36 | Correct | 1 ms | 2396 KB | n = 81, m = 6 |
37 | Correct | 1 ms | 2392 KB | n = 98, m = 7 |
38 | Correct | 1 ms | 2392 KB | n = 92, m = 7 |
39 | Correct | 1 ms | 2396 KB | n = 88, m = 21 |
40 | Correct | 1 ms | 2396 KB | n = 90, m = 21 |
41 | Correct | 0 ms | 2396 KB | n = 98, m = 22 |
42 | Incorrect | 1 ms | 2396 KB | char #0 differ - expected: '?', found: '_' |
43 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2392 KB | n = 13, m = 1 |
2 | Correct | 1 ms | 2396 KB | n = 18, m = 1 |
3 | Correct | 0 ms | 2396 KB | n = 17, m = 1 |
4 | Correct | 1 ms | 2396 KB | n = 1, m = 1 |
5 | Correct | 1 ms | 2396 KB | n = 20, m = 1 |
6 | Correct | 0 ms | 2396 KB | n = 20, m = 1 |
7 | Correct | 1 ms | 2396 KB | n = 20, m = 1 |
8 | Correct | 1 ms | 2396 KB | n = 20, m = 5 |
9 | Correct | 0 ms | 2396 KB | n = 18, m = 3 |
10 | Correct | 1 ms | 2396 KB | n = 17, m = 2 |
11 | Correct | 0 ms | 2396 KB | n = 20, m = 2 |
12 | Correct | 1 ms | 2396 KB | n = 17, m = 4 |
13 | Correct | 0 ms | 2396 KB | n = 17, m = 6 |
14 | Correct | 1 ms | 2396 KB | n = 17, m = 1 |
15 | Correct | 1 ms | 2392 KB | n = 17, m = 4 |
16 | Correct | 1 ms | 2396 KB | n = 13, m = 3 |
17 | Correct | 1 ms | 2396 KB | n = 18, m = 4 |
18 | Correct | 1 ms | 2396 KB | n = 20, m = 10 |
19 | Correct | 1 ms | 2396 KB | n = 19, m = 10 |
20 | Correct | 1 ms | 2392 KB | n = 100, m = 5 |
21 | Correct | 1 ms | 2396 KB | n = 90, m = 3 |
22 | Correct | 1 ms | 2396 KB | n = 86, m = 2 |
23 | Correct | 1 ms | 2396 KB | n = 81, m = 4 |
24 | Correct | 1 ms | 2392 KB | n = 89, m = 10 |
25 | Correct | 1 ms | 2396 KB | n = 81, m = 23 |
26 | Correct | 1 ms | 2396 KB | n = 86, m = 8 |
27 | Correct | 1 ms | 2396 KB | n = 53, m = 22 |
28 | Correct | 1 ms | 2396 KB | n = 89, m = 35 |
29 | Correct | 1 ms | 2396 KB | n = 63, m = 25 |
30 | Correct | 1 ms | 2396 KB | n = 100, m = 50 |
31 | Correct | 1 ms | 2396 KB | n = 99, m = 50 |
32 | Correct | 1 ms | 2392 KB | n = 13, m = 4 |
33 | Correct | 1 ms | 2396 KB | n = 86, m = 2 |
34 | Correct | 1 ms | 2396 KB | n = 88, m = 2 |
35 | Correct | 1 ms | 2396 KB | n = 86, m = 2 |
36 | Correct | 1 ms | 2396 KB | n = 81, m = 6 |
37 | Correct | 1 ms | 2392 KB | n = 98, m = 7 |
38 | Correct | 1 ms | 2392 KB | n = 92, m = 7 |
39 | Correct | 1 ms | 2396 KB | n = 88, m = 21 |
40 | Correct | 1 ms | 2396 KB | n = 90, m = 21 |
41 | Correct | 0 ms | 2396 KB | n = 98, m = 22 |
42 | Incorrect | 1 ms | 2396 KB | char #0 differ - expected: '?', found: '_' |
43 | Halted | 0 ms | 0 KB | - |