Submission #652742

#TimeUTC-0UsernameProblemLanguageResultExecution timeMemory
6527422022-10-24 04:51:13alvinpiterPaint By Numbers (IOI16_paint)C++14
100 / 100
228 ms85188 KiB
/*
color -> 0 means white, 1 means black
dpPrefix[j][k][color] -> Can the first j character obey the first k rules such that the j-th character is painted "color"
dpSuffix[j][k][color] -> Can the suffix starting from j-th character obey the rules starting from the k-th such that s[j] is painted "color"
For each index j, define:
canBlack[j] -> > 0 if there is a solution such that s[j] is painted black, 0 otherwise.
canWhite[j] -> > 0 if there is a solution such that s[j] is painted white, 0 otherwise.
canBlack[j] = dpPrefix[j][k][1] && dpSuffix[j + 1][k + 1][0]
canWhite[j] = dpPrefix[j][k][0] && (dpSuffix[j + 1][k + 1][0] || dpSuffix[j + 1][k + 1][1])
Try every possible k.
Complexity: O(NK)
*/
#include "paint.h"
#include<bits/stdc++.h>
using namespace std;
#define MAXN 200000
#define MAXK 100
bool dpPrefix[MAXN + 3][MAXK + 3][2], dpSuffix[MAXN + 3][MAXK + 3][2];
int canBlack[MAXN + 3], canWhite[MAXN + 3];
int cntBlack[MAXN + 3], cntWhite[MAXN + 3];
std::string solve_puzzle(std::string s, std::vector<int> c) {
int N = s.length();
int K = c.size();
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:93:10: warning: unused variable 'canBeBlack' [-Wunused-variable]
   93 |     bool canBeBlack = false, canBeWhite = false;
      |          ^~~~~~~~~~
paint.cpp:93:30: warning: unused variable 'canBeWhite' [-Wunused-variable]
   93 |     bool canBeBlack = false, canBeWhite = false;
      |                              ^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...