This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "paint.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
#define pb push_back
#define mk make_pair
#define X real()
#define Y imag()
#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define MOD 1000000007
#define MOD1 1000000009
#define sqr(x) sqr((x)*(x))
void debug_out() { cerr << endl; }
template<typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << ' ' << H; debug_out(T...); }
#ifdef BE_DEBUG
#define debug(...) cerr << "\033[1;31m(" << #__VA_ARGS__ << "):\033[0m", debug_out(__VA_ARGS__)
#else
#define debug(...)
#endif
map<int,bool> mp[100005];
map<ll,bool> mm;
int dp[1005];
vector<int> v[30];
int l,r;
int mn;
int z[30];
int level;
void dfs(int k, int x) {
int yy = z[level-k] * x;
int zz = z[level-k] * (x + 1) - 1;
if(l <= yy && zz <= r) {
mn = min (mn,v[k][x]);
return;
}
if(zz < l || yy > r || k == level) return;
dfs(k + 1, x * 2);
dfs(k + 1, x * 2 + 1);
}
void update(int pos, int val) {
v[level][pos] = val;
for(int i = level - 1; i >= 0; i --) {
pos/=2;
v[i][pos] = min(v[i + 1][pos * 2],v[i + 1][pos * 2 + 1]);
}
}
int minimumInstructions( int N, int M, int K, std::vector<int> C, std::vector<int> A, std::vector<std::vector<int>> B) {
bool sub_1 = 0;
for(int i = 0; i < B.size(); i ++) {
// if(B[i].size() > 1) sub_1 = 1;
}
if(sub_1 == 0) {
// subtask 1
ll zereg[N + 5];
zereg[0] = 1;
for(int i = 1; i <= N; i ++) {
zereg[i] = (zereg[i - 1] * 10) % MOD;
}
//
ll hash_val[M + 5];
hash_val[0] = 0;
for(int i = 0; i < M; i ++) {
hash_val[0] = (hash_val[0] * 10 + B[i][0]) % MOD;
}
for(int i = 0; i < M; i ++) {
hash_val[i + 1] = ((hash_val[i] - (B[i][0] * zereg[M - 1]) % MOD + MOD) % MOD * 10 + B[i][0]) % MOD;
}
for(int i = 0; i < M; i ++) {
mm[hash_val[i]] = 1;
debug(hash_val[i]);
}
//
z[0] = 1;
for(int i = 0; i < 30; i ++) {
if(z[i] >= N) {
level = i;
break;
}
z[i + 1] = z[i] * 2;
}
for(int i = 0; i <= level; i ++) {
for(int j = 0; j < z[i]; j ++) {
v[i].pb(1e9 + 7);
}
}
//
ll h[N + 5];
for(int i = 0; i < N; i ++) {
if(i == 0) h[i] = C[i];
else {
h[i] = (h[i - 1] * 10 + C[i]) % MOD;
}
debug(h[i]);
}
//
for(int i = M - 1; i < N; i ++) {
ll cur_hash = h[i];
if(i != M - 1) {
cur_hash = (h[i] - (h[i - M] * zereg[M]) % MOD + MOD) % MOD;
}
debug(cur_hash);
if(mm[cur_hash] == 1) {
//debug("WTF");
if(i == M - 1) {
update(i,1);
continue;
}
l = i - M;
r = i - 1;
debug(i);
//cout << l << ' ' << r << '\n';
mn = 1e9 + 7;
dfs(0,0);
update(i,mn + 1);
}
}
/*
for(int i = 0; i<= level; i ++) {
for(int j = 0; j < v[i].size(); j ++) {
cout << v[i][j] << ' ';
}
cout << '\n';
}
*/
if(v[level][N - 1] >= 1e9) {
return -1;
}
return v[level][N - 1];
}
for(;;);
for(int i = 0; i < B.size(); i ++) {
for(int j = 0; j < B[i].size(); j ++) {
mp[i][B[i][j]] = 1;
}
}
for(int i = M - 1; i < N; i ++) {
int l = i - M + 1;
int r = i;
int starter = 0;
bool check = 0;
while(starter < M) {
int cur = starter;
bool ok = 0;
for(int j = l; j <= r; j ++) {
if(mp[cur][C[j]] == 0) {
ok = 1;
break;
}
cur ++;
if(cur == M) cur = 0;
}
if(ok == 0) {
check = 1;
break;
}
starter ++;
}
if(check == 0) {
continue;
}
if(i == M - 1) {
dp[i] = 1;
continue;
}
int mn = 1e9;
for(int j = i - 1; j >= i - M; j --) {
if(dp[j] == 0) continue;
mn = min(mn,dp[j]);
}
if(mn != 1e9) {
mn ++;
dp[i] = mn;
}
}
if(dp[N - 1] == 0) return -1;
return dp[N - 1];
}
Compilation message (stderr)
paint.cpp: In function 'int minimumInstructions(int, int, int, std::vector<int>, std::vector<int>, std::vector<std::vector<int> >)':
paint.cpp:60:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
60 | for(int i = 0; i < B.size(); i ++) {
| ~~^~~~~~~~~~
paint.cpp:143:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
143 | for(int i = 0; i < B.size(); i ++) {
| ~~^~~~~~~~~~
paint.cpp:144:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
144 | for(int j = 0; j < B[i].size(); j ++) {
| ~~^~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |