oj.uz

Submission #74234

# Submission time Handle Problem Language Result Execution time Memory
74234 2018-08-30T14:10:19 Z renatsj Paint By Numbers (IOI16_paint) C++14
32 / 100
 2 ms 736 KB 
#include "paint.h"
#include<bits/stdc++.h>
#include <cstdlib>
using namespace std;
int i,j,n,m,dp[300005][103],dp2[300005][103],prewhite[300005],preblack[300005],sufwhite[300005],sufblack[300005],canbewhite[300005],canbeblack[300005],liel1,liel2,liel;
list<int> x;
string solve_puzzle(string s, vector<int> c)
{
    n=s.size();
    m=c.size();
    i=1;
    while (i<=n)
    {
        prewhite[i]=prewhite[i-1];
        preblack[i]=preblack[i-1];
        if (s[i-1]=='X')
        {
            preblack[i]++;
        }
        if (s[i-1]=='_')
        {
            prewhite[i]++;
        }
        i++;
    }
    i=n;
    while (i>=1)
    {
        sufwhite[i]=sufwhite[i+1];
        sufblack[i]=sufblack[i+1];
        if (s[i-1]=='X')
        {
            sufblack[i]++;
        }
        if (s[i-1]=='_')
        {
            sufblack[i]++;
        }
        i--;
    }
    /*dp[0][0]=1;
    dp[0][1]=1;
    dp[0][2]=1;
    j=3;
    while (j<=n+2&&s[j-3]!='X')
    {
        dp[0][j]=1;
        j++;
    }
    dp2[0][n+1]=1;
    dp2[0][n]=1;
    dp2[0][n+2]=1;
    j=n-1;
    while (j>=0&&s[j]!='X')
    {
        dp2[0][j]=1;
        j++;
    }*/
    /*j=0;
    while (j<=n+2)
    {
        dp[0][j]=1;
        dp2[0][j]=1;
        j++;
    }*/
    j=0;
    while (j<=n+2)
    {
        //dp[0][j]=1;
        dp2[0][j]=1;
        j++;
    }
    dp[0][0]=1;
    dp[0][1]=1;
    dp[0][2]=1;
    j=3;
    while (j<=n+2&&s[j-3]!='X')
    {
        dp[0][j]=1;
        j++;
    }

    i=1;
    while (i<=m)
    {
        j=1;
        while (j<=n)
        {
            if (s[j-1]=='_')
            {
                dp[i][j]=dp[i][j-1];
            }
            else if (s[j-1]=='X')
            {
                if (prewhite[j]==prewhite[j-c[i-1]]&&j-c[i-1]-1>=0)
                {
                    if (i==1&&j-c[i-1]==0)
                    {
                        dp[i][j]=1;
                    }
                    else
                    {
                        dp[i][j]=dp[i-1][j-c[i-1]-1];
                    }
                }
            }
            else
            {
                if (i==1&&j-c[i-1]==0)
                {
                    dp[i][j]=1;
                }
                else if (j-c[i-1]<=0)
                {

                }
                else
                {
                    dp[i][j]=dp[i][j-1]||dp[i-1][j-c[i-1]-1];
                }
            }
            //cout << i << " " << j << " " << dp[i][j] << "\n";
            //cout << dp[i][j] << " ";
            j++;
        }
        //cout << "\n";
        i++;
    }
    for (int j:c)
    {
        x.push_front(j);
    }
    c.clear();
    for (int j:x)
    {
        c.push_back(j);
        //cout << j << " ";
    }
    x.clear();
    //cout << "\n";
    i=1;
    while (i<=m)
    {
        j=n;
        while (j>=1)
        {
            if (s[j-1]=='_')
            {
                dp2[i][j]=dp2[i][j+1];
            }
            else if (s[j-1]=='X')
            {
                if (sufwhite[j]==sufwhite[j+c[i-1]])
                {
                    dp2[i][j]=dp2[i-1][j+c[i-1]+1];
                }
            }
            else
            {
                dp2[i][j]=dp2[i][j+1]||dp2[i-1][j+c[i-1]+1];
            }
            //cout << i << " " << j << " " << dp2[i][j] << " " << c[i-1] << "\n";
            //cout << dp[i][j] << " ";
            j--;
        }
        //cout << "\n";
        i++;
    }
    i=1;
    while (i<=m)
    {
        j=1;
        while (j<=n)
        {
            //cout << dp2[i][j] << " ";
            j++;
        }
        //cout << "\n";
        i++;
    }
    j=1;
    while (j<=n)
    {
        if (s[j-1]=='.')
        {
            canbewhite[j]=1;
            canbeblack[j]=1;
        }
        else if (s[j-1]=='X')
        {
            canbeblack[j]=1;
            canbewhite[j]=0;
        }
        else
        {
            canbeblack[j]=0;
            canbewhite[j]=1;
        }
        i=0;
        while (i<=m)
        {
            if (dp[i][j-1]==1)
            {
                liel1=i;
            }
            if (dp2[i][j+1]==1)
            {
                liel2=i;
            }
            i++;
        }
        //cout << j << " " << liel1 << " " << liel2 << "\n";
        if (liel1+liel2<m)
        {
            canbewhite[j]=0;
        }
        if (canbewhite[j]==0&&canbeblack[j]==1)
        {
            s[j-1]='X';
        }
        if (canbewhite[j]==1&&canbeblack[j]==0)
        {
            s[j-1]='_';
        }
        j++;
    }
    i=1;
    while (i<=n)
    {
        prewhite[i]=prewhite[i-1];
        preblack[i]=preblack[i-1];
        if (s[i-1]=='X')
        {
            preblack[i]++;
        }
        if (s[i-1]=='_')
        {
            prewhite[i]++;
        }
        //cout << canbewhite[i] << " " << canbeblack[i] << "  " << prewhite[i] << " " << preblack[i] << "\n";
        i++;
    }
    for (int j:c)
    {
        x.push_front(j);
    }
    c.clear();
    for (int j:x)
    {
        c.push_back(j);
        //cout << j << " ";
    }
    liel=-1;
    j=1;
    while (j<=n)
    {
        i=0;
        while (i<m)
        {
            //cout << i << " " << j << " " << liel << "  ";
            //cout << j << " " << j+c[i]-1 << " " << s[j+c[i]-1] << " ";
            //cout << prewhite[j] << " " << prewhite[j+c[i]-1] << " ";
            //cout << dp[i][j-1] << " " << dp2[m-i][j+1] << "\n";
            if ((j==1||s[j-2]!='X')&&j+c[i]-1<=s.size()&&(s[j+c[i]-1]!='X')&&prewhite[j]==prewhite[j+c[i]-1]&&dp[i][j-1]==1&&dp2[m-i-1][j+1]==1)
            {
                liel=j+c[i]-1;
            }
            i++;
        }
        if (liel>=j)
        {
            canbeblack[j]=2;
        }
        j++;
    }
    string sss;
    j=1;
    while (j<=n)
    {
        if (canbeblack[j]==2&&canbewhite[j]==1)
        {
            sss+='?';
        }
        else if (canbeblack[j]==2)
        {
            sss+='X';
        }
        else
        {
            sss+='_';
        }
        //cout << canbeblack[j] << " " << canbewhite[j] << "\n";
        j++;
    }
    return sss;
}

Compilation message

paint.cpp: In function 'std::__cxx11::string solve_puzzle(std::__cxx11::string, std::vector<int>)':
paint.cpp:264:46: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if ((j==1||s[j-2]!='X')&&j+c[i]-1<=s.size()&&(s[j+c[i]-1]!='X')&&prewhite[j]==prewhite[j+c[i]-1]&&dp[i][j-1]==1&&dp2[m-i-1][j+1]==1)
                                      ~~~~~~~~^~~~~~~~~~

Subtask #1
7.0 / 7.0

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

Subtask #2
3.0 / 3.0

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

Subtask #3
22.0 / 22.0

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

Subtask #4
0 / 27.0

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

Subtask #5
0 / 21.0

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

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

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