#include "paint.h"
#include <iostream>
#include <iomanip>
#include <chrono>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <set>
#include <map>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <utility>
#include <string>
#include <vector>
#include <bitset>
using std::min;
using std::max;
using std::sort;
using std::swap;
using std::fixed;
using std::to_string;
using std::make_pair;
using std::upper_bound;
using std::lower_bound;
using std::setprecision;
using std::cin;
using std::cout;
using std::set;
using std::map;
using std::list;
using std::pair;
using std::less;
using std::tuple;
using std::stack;
using std::queue;
using std::deque;
using std::string;
using std::vector;
using std::bitset;
using std::greater;
using std::priority_queue;
typedef long double ld;
typedef unsigned ui;
typedef long long lli;
typedef unsigned long long ulli;
typedef vector<int32_t> vi;
typedef vector<ld> vld;
typedef vector<ui> vui;
typedef vector<lli> vlli;
typedef vector<ulli> vulli;
typedef list<int32_t> lsi;
typedef list<ld> lsld;
typedef list<ui> lsui;
typedef list<lli> lslli;
typedef list<ulli> lsulli;
typedef set<int32_t> si;
typedef set<ld> sld;
typedef set<ui> sui;
typedef set<lli> slli;
typedef set<ulli> sulli;
typedef pair<int32_t, int32_t> pii;
typedef pair<lli, lli> pll;
// #define int int64_t
#define endl "\n"
#define inp(n) int n; cin >> n
#define Inp(n) lli n; cin >> n
#define inpstr(s) string s; cin >> s
#define inp2(a,b) int a,b; cin >> a >> b
#define Inp2(a,b) lli a,b; cin >> a >> b
#define inparr(arr,n) int arr[n]; f0(t_ind, n) cin >> arr[t_ind]
#define Inparr(arr,n) lli arr[n]; f0(t_ind, n) cin >> arr[t_ind]
#define f0(i,n) for(int32_t i = 0; i < (n); i++)
#define f1(i,n) for(int32_t i = 1; i <= (n); i++)
#define rep0(i,l,r) for(int32_t i=(l); i < (r); i++)
#define rep1(i,l,r) for(int32_t i=(l); i <= (r); i++)
#define testIn cin >> test
#define tests for(int32_t testNo=1; testNo <= (test); testNo++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define asrt(v) sort(all(v))
#define dsrt(v) sort(rall(v))
#define revStr(str) string(rall(str))
#define len(a) ((int64_t)(a).size())
#define front_zero(n) __builtin_clzll(n)
#define back_zero(n) __builtin_ctzll(n)
#define total_one(n) __builtin_popcountll(n)
#define lcm(a, b) (((a)*(b))/gcd(a,b))
#define mem(a, b) memset(a, b, sizeof(a))
#define pb push_back
#define pf push_front
#define mp make_pair
#define ff first
#define ss second
#define yes cout << "yes" << endl
#define no cout << "no" << endl
#define Yes cout << "Yes" << endl
#define No cout << "No" << endl
#define YES cout << "YES" << endl
#define NO cout << "NO" << endl
#define finish return 0
#define clean fflush(stdout)
#define Inf (int32_t)(1e9)
#define INF (lli)(1e18)
#define Eps (ld)(1e-9)
#define EPS (ld)(1e-18)
#define PI (ld)(3.141592653589793238462643383279502884197169L)
#define MOD (int32_t)(1e9+7)
#define MXN (int32_t)(1e5+7)
int likedby[100005];
// int likedby2[100005];
int minimumInstructions(
int N, int M, int K, std::vector<int> C,
std::vector<int> A, std::vector<std::vector<int>> B) {
bool valid[N] = {0};
int lstvalid[N];
int cur = -1, ans = 0;
f0(i, 100005) likedby[i] = -1;
f0(i, M) {
f0(j, A[i]) {
likedby[B[i][j]] = i;
}
}
f0(i, N) {
if(likedby[C[i]] == -1) return -1;
if(i != 0) {
int df = likedby[C[i]] - likedby[C[i-1]];
df %= M;
df += M;
df %= M;
if(df != 1) {
cur = i;
}
lstvalid[i] = cur;
} else {
lstvalid[i] = i;
}
}
cur = 0;
while(cur < N) {
if(lstvalid[cur] == -1) return -1;
if(lstvalid[cur] < cur - M + 1) return -1;
ans++;
cur = lstvalid[cur] + M;
}
return ans;
// vector<si> B(M);
// f0(i, M) {
// for(int c: bbb[i]) B[i].insert(c);
// }
// bool valid[N] = {0};
// int lstvalid[N];
f0(st, M) {
int lstbreak = -1;
f0(i, N) {
// int color = C[i];
auto it = lower_bound(B[(st+i)%M].begin(), B[(st+i)%M].end(), C[i]);
if (it == B[(st+i)%M].end()) {
lstbreak = i;
} else if ((*it) != C[i]) {
lstbreak = i;
}
if(i - lstbreak >= M) {
valid[i - M + 1] = true;
}
}
}
cur = -1, ans = 0;
f0(i, N) {
if(valid[i]) {
cur = i;
}
lstvalid[i] = cur;
}
cur = 0;
while(cur < N) {
if(lstvalid[cur] == -1) return -1;
if(lstvalid[cur] < cur - M + 1) return -1;
ans++;
cur = lstvalid[cur] + M;
}
return ans;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
596 KB |
Output is correct |
| 2 |
Correct |
1 ms |
596 KB |
Output is correct |
| 3 |
Correct |
1 ms |
596 KB |
Output is correct |
| 4 |
Correct |
1 ms |
596 KB |
Output is correct |
| 5 |
Correct |
1 ms |
596 KB |
Output is correct |
| 6 |
Incorrect |
1 ms |
596 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
596 KB |
Output is correct |
| 2 |
Correct |
1 ms |
596 KB |
Output is correct |
| 3 |
Correct |
1 ms |
596 KB |
Output is correct |
| 4 |
Correct |
1 ms |
596 KB |
Output is correct |
| 5 |
Correct |
1 ms |
596 KB |
Output is correct |
| 6 |
Incorrect |
1 ms |
596 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
596 KB |
Output is correct |
| 2 |
Correct |
1 ms |
596 KB |
Output is correct |
| 3 |
Correct |
1 ms |
596 KB |
Output is correct |
| 4 |
Correct |
1 ms |
596 KB |
Output is correct |
| 5 |
Correct |
1 ms |
596 KB |
Output is correct |
| 6 |
Incorrect |
1 ms |
596 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
596 KB |
Output is correct |
| 2 |
Correct |
1 ms |
596 KB |
Output is correct |
| 3 |
Correct |
1 ms |
596 KB |
Output is correct |
| 4 |
Correct |
1 ms |
596 KB |
Output is correct |
| 5 |
Correct |
1 ms |
596 KB |
Output is correct |
| 6 |
Incorrect |
1 ms |
596 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
596 KB |
Output is correct |
| 2 |
Correct |
1 ms |
596 KB |
Output is correct |
| 3 |
Correct |
1 ms |
596 KB |
Output is correct |
| 4 |
Correct |
1 ms |
596 KB |
Output is correct |
| 5 |
Correct |
1 ms |
596 KB |
Output is correct |
| 6 |
Incorrect |
1 ms |
596 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
