Submission #1222619

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222619		walizamanee	Paint By Numbers (IOI16_paint)	C++20	90 / 100	250 ms	565580 KiB

paint

#include<bits/stdc++.h>
#include "paint.h"
#include <cstdlib>
using namespace std;



int shuru[200002][201][2] , shesh[200002][201][2] , one , two; // black and white
int ans[200002] , sum[200002];
string solve_puzzle(string s, vector<int> c) {

    int n = (int)s.size();
    int k = (int)c.size();
    for( int z = 0; z <= n + 1; z++ ) {
        for( int y = 0; y <= k + 1; y++ ) {
            shuru[z][y][0] = 0;
            shesh[z][y][0] = 0;
            shuru[z][y][1] = 0;
            shesh[z][y][1] = 0;
        }
    }
    shuru[0][0][1] = 1;
    shesh[n + 1][k + 1][1] = 1;
    one = 0;
    two = 0;
    for( int z = 1; z <= n; z++ ) {
        if( s[z - 1] == 'X' ) {
            for( int y = 1; y <= k; y++ ) {
                if( z >= c[y - 1] && (z - two) >= c[y - 1] ) shuru[z][y][0] = shuru[z - c[y - 1]][y - 1][1];
            }
        }
        else if( s[z - 1] == '_' ) {
            for( int y = 0; y <= k; y++ ) shuru[z][y][1] = max(shuru[z - 1][y][0] , shuru[z - 1][y][1]);    //karon black oir whtie hote pare
            two = z;
        }
        else{
            for( int y = 1; y <= k; y++ ) {
                if( z >= c[y - 1] && (z - two) >= c[y - 1] ) shuru[z][y][0] = shuru[z - c[y - 1]][y - 1][1];
            }
            for( int y = 0; y <= k; y++ ) shuru[z][y][1] = max(shuru[z - 1][y][0] , shuru[z - 1][y][1]);
        }
    }
    two = n + 1;
    for( int z = n; z >= 1; z-- ) {
        if( s[z - 1] == 'X' ) {
            for( int y = k; y >= 1; y-- ) {
                if(  (z + ( c[y - 1] - 1)) <= n &&  (two - z) >= c[y - 1] ) shesh[z][y][0] = shesh[z + c[y - 1]][y + 1][1];
            }
        }
        else if( s[z - 1] == '_' ) {
            for( int y = 1; y <= k + 1; y++ ) shesh[z][y][1] = max(shesh[z + 1][y][0] , shesh[z + 1][y][1]);    //karon black oir whtie hote pare
            two = z;
        }

        else{
            for( int y = k; y >= 1; y-- ) {
                if(  (z + ( c[y - 1] - 1)) <= n &&  (two - z) >= c[y - 1] ) shesh[z][y][0] = shesh[z + c[y - 1]][y + 1][1];
            }
            for( int y = 1; y <= k + 1; y++ ) shesh[z][y][1] = max(shesh[z + 1][y][0] , shesh[z + 1][y][1]);    //karon black oir whtie hote pare

        }
    }
   /* for( int z = 1; z <= n; z++ ) {
        cerr << z << "\n";
        for( int y = 0; y <= k; y++ ) cerr << shuru[z][y][0] << " ";
        for( int y = 0; y <= k; y++ ) cerr << shuru[z][y][1] << " ";
        cerr << "\n";
    } 
    for( int z = 1; z <= n; z++ ) {
        cerr << z << "\n";
        for( int y = 0; y <= k + 1; y++ ) cerr << shesh[z][y][0] << " ";
        for( int y = 0; y <= k + 1; y++ ) cerr << shesh[z][y][1] << " ";
        cerr << "\n";
    } */
    for( int z = 1; z <= n; z++  ) {
         sum[z] = 0;
         ans[z] = 0;

    }
    for( int z = 1; z <= n; z++ ) {
        for( int y = 1; y <= k; y++ ) {
            if( shuru[z][y][0] == 1 && shesh[z + 1][y + 1][1] == 1 ) {
                sum[z + 1]--;
                sum[z - (c[y - 1]) + 1]++;
            }
        }
        if( s[z - 1] != 'X' ) {
        for( int y = 0; y <= k; y++ ) {
            if( (max( shuru[z - 1][y][0] , shuru[z - 1][y][1] ) == 1) &&
              (max( shesh[z + 1][y + 1][0] , shesh[z + 1][y + 1][1] ) == 1) ) ans[z] = 2;
        }
        }
    }
    int jog = 0;
    for( int z = 1; z <= n; z++ ) {
        jog += sum[z];
        if( jog > 0 ) ans[z] = (ans[z] | 1);
       // cerr << jog << " ";
    }
   // cerr << "\n";
    string uttor = s;
    for( int z = 1; z <= n; z++ ) {
        if( ans[z] == 1 ) uttor[z - 1] = 'X';
        else if( ans[z] == 2 ) uttor[z - 1] = '_';
        else if( ans[z] == 3 ) uttor[z - 1] = '?'; 
    }
    return uttor;
}

Compilation message (stderr)

paint.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
paint_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

• Subtask 1: 7 / 7
• Subtask 2: 3 / 3
• Subtask 3: 22 / 22
• Subtask 4: 27 / 27
• Subtask 5: 21 / 21
• Subtask 6: 10 / 10
• Subtask 7: 0 / 10