Submission #551171

#	Time	Username	Problem	Language	Result	Execution time	Memory
551171		truc12a2cvp	Painting Walls (APIO20_paint)	C++14	0 / 100	7 ms	10068 KiB

paint

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> II;
const int maxn = 1e5 + 5, logN = 20;
const int MOD = 1e9 + 7;
const ll INF = 1e9;

int n, m, k, c[maxn], ok[maxn];
vector<int> g[maxn], f[maxn];

int minimumInstructions(int N, int M, int K, vector<int> C, vector<int> A, vector<vector<int>> B){
       n = N;
       m = M;
       k = K;
       for(int i = 1; i <= n; i ++) c[i] = C[i - 1];
       for(int i = 0; i < m; i ++){
              for(int j = 0; j < A[i]; j ++){
                     g[B[i][j]].push_back(i);
              }
       }
       for(int i = 1; i <= n; i ++){
              f[i].resize(g[c[i]].size());
              for(int j = 0; j < (int)f[i].size(); j ++){
                     f[i][j] = 1;
                     if(i != 1){
                          int pos = g[c[i]][j];
                          int p = lower_bound(g[c[i - 1]].begin(), g[c[i - 1]].end(), (pos - 1 + m) % m) - g[c[i - 1]].begin();
                          if(g[c[i - 1]][p] == (pos - 1 + m) % m) f[i][j] += f[i - 1][p];
                     }
                     if(f[i][j] >= m) ok[i - m + 1] = true;
              }
       }
       if(!ok[1]) return -1;
       int cur = m, res = 1;
       while(cur < n){
              bool flag = false;
              for(int i = cur + 1; i > cur - m + 1; i --){
                     if(ok[i]){
                            res ++;
                            cur = i + m - 1;
                            flag = true;
                            break;
                     }
              }
              if(!flag) return -1;
       }
       return res;
}
/*
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout << minimumInstructions(1, 1, 1, {0}, {1}, {{0}}) << endl;
    return 0;
}
*/

• Subtask 1: 0 / 12
• Subtask 2: 0 / 15
• Subtask 3: 0 / 13
• Subtask 4: 0 / 23
• Subtask 5: 0 / 37