Submission #930260

#	Time	Username	Problem	Language	Result	Execution time	Memory
930260		VinhLuu	Painting Walls (APIO20_paint)	C++17	100 / 100	372 ms	16468 KiB

paint

#include <bits/stdc++.h>
//#define int long long
//#define ll long long
#define fi first
#define se second
#define pb push_back
using namespace std;

typedef pair<int,int> pii;
typedef tuple<int,int,int> tp;
const int N = 1e5 + 5;
const int oo = 1e9;
const int mod = 998244353; // 1e9 + 7;
const int M = 5e5 + 5;

bool g[N];
int st[N << 1], f[2][N], dp[N];
vector<int> p[N];

void update(int i,int x, int n){
    i += n - 1;
    st[i] = x;
    while(i > 1){
        i /= 2;
        st[i] = min(st[i << 1], st[i << 1|1]);
    }
}

int get(int l,int r,int n){
    r++;
    int ret= oo;
    for(l += n - 1, r += n - 1; l < r; l /= 2, r /= 2){
        if(l & 1) ret = min(ret, st[l++]);
        if(r & 1) ret = min(ret, st[--r]);
    }
    return ret;
}

int minimumInstructions(int n, int m, int k, vector<int> C, vector<int> A, vector<vector<int>> B){
    for(int i = 0; i < m; i ++) for(auto j : B[i]) p[j].pb(i);
    memset(f, -1, sizeof(f));
    for(int i = 1; i <= n; i ++) dp[i] = oo;

    for(int i = 1; i <= 2 * n; i ++) st[i] = oo;

    int pre = 0, nx = 1;

    bool afk = false;

    for(int i = n; i >= 1; i --){
        for(auto j : p[C[i - 1]]){
            if(f[pre][(j + 1) % m] == -1) f[nx][j] = i;
            else f[nx][j] = f[pre][(j + 1) % m];
//            if(i == 6) cout << j << " " << (j + 1) % m << " " <<  f[pre][(j + 1) % m] << " k\n";
            if(f[nx][j] - i + 1 >= m) g[i] = true;
        }

        if(i < n) for(auto j : p[C[i]]) f[pre][j] = -1;
//        cout << i << "check\n";
        for(auto j : p[C[i - 1]]){
            f[pre][j] = f[nx][j];
//            cout << j << " " << f[nx][j] << " f\n";
            f[nx][j] = -1;
        }

//        cout << i << " o\n";
//        for(int j = 0; j < m; j ++) cout << j << " " << f[pre][j] << "ff\n";
//        cout << i << " " << g[i] << " g\n";
        if(g[i] == true){

            if(i + m > n) dp[i] = 1;
            dp[i] = min(dp[i], get(i + 1, min(i + m, n), n) + 1);
            update(i, dp[i], n);
//        cout << "fffffff " << i << " " << min(i + m, n) << " " << dp[i] << " \n";
//            afk = true;
        }
    }

//    if(dp[1] >= (int)1e9) return -1;
//    else
        return (dp[1] >= oo ? -1 : dp[1]);
}

//#define LOCAL

#ifdef LOCAL
signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    #define task "v"
    if(fopen(task ".inp","r")){
        freopen(task ".inp","r",stdin);
        freopen(task ".out","w",stdout);
    }

     int n, m, k; cin >> n >> m >> k;
  vector<int> C, A;
  vector<vector<int>> B;
  for (int i = 1; i <= n; ++i) {
    int x; cin >> x;
    C.push_back(x);
  }
  for (int i = 1; i <= m; ++i) {
    int a; cin >> a; A.push_back(a);
    vector<int> vt;
    for (int j = 1; j <= a; ++j) {
      int x; cin >> x;
      vt.push_back(x);
    }
    sort(vt.begin(), vt.end());
    B.push_back(vt);

  }
  cout << minimumInstructions(n, m, k, C, A, B);
}
#endif // LOCAL

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:48:10: warning: unused variable 'afk' [-Wunused-variable]
   48 |     bool afk = false;
      |          ^~~

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