Submission #568896

#	Time	Username	Problem	Language	Result	Execution time	Memory
568896		NemanjaSo2005	Paint By Numbers (IOI16_paint)	C++14	80 / 100	385 ms	840 KiB

paint

#include "paint.h"
#include <cstdlib>
#include<bits/stdc++.h>
#define ll long long
using namespace std;
vector<int> blokovi;
string A,R;
bool dp[200005][105];
ll N,K,prefiks[105];
bool moguce(string B){
   //cout<<"MOGUCE? "<<B.substr(1,N)<<endl;
   int pbela=0;
   for(int i=1;i<=N;i++)
      for(int j=1;j<=K;j++)
         dp[i][j]=0;
   for(int i=1;i<=N;i++){
      if(B[i]=='_')
         pbela=i;
      if(B[i-blokovi[1]]=='X'){
         break;
      }
      if(i-blokovi[1]<pbela)
         continue;
      dp[i][1]=1;
   }
   pbela=0;
   for(int i=1;i<=N;i++){
      if(B[i]=='_')
         pbela=i;
      for(int j=2;j<=K;j++){
         if(i<prefiks[j])
            break;
         if(i-blokovi[j]<pbela)
            continue;
         if(B[i-blokovi[j]]=='X')
            continue;
         for(int i2=i-blokovi[j]-1;i2>=1;i2--){
            if(dp[i2][j-1]){
               dp[i][j]=1;
               break;
            }
            if(B[i2]=='X')
               break;
         }
      }
   }
  /* for(int j=1;j<=K;j++){
      for(int i=1;i<=N;i++)
         cout<<dp[i][j]<<" ";
      cout<<endl;
   }*/
   for(int i=N;i>=1;i--){
      if(dp[i][K]==1){
    //     cout<<"JESTE"<<endl;
         return true;
      }
      if(B[i]=='X')
         break;
   }
   //cout<<"NIJE"<<endl;
   return false;
}
string solve_puzzle(string s, vector<int> c) {
   N=s.size();
   K=c.size();
   blokovi.push_back(0);
   for(int i=0;i<K;i++)
      blokovi.push_back(c[i]);
   A="`"+s+"````";
   prefiks[0]=-1;
   for(int i=1;i<=K;i++)
      prefiks[i]=prefiks[i-1]+1+blokovi[i];
   prefiks[0]=0;
   /*while(true){
      cin>>s;
      A="`"+s+"````";
      cout<<moguce(A)<<endl;
   }*/
   for(int i=1;i<=N;i++){
      if(A[i]!='.'){
         R.push_back(A[i]);
         continue;
      }
      int v=0;
      A[i]='X';
      if(moguce(A))
         v++;
      A[i]='_';
      if(moguce(A))
         v--;
      A[i]='.';
      if(v==1)
         R.push_back('X');
      if(v==0)
         R.push_back('?');
      if(v==-1)
         R.push_back('_');
   }
   return R;
}

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