Submission #979692

#TimeUsernameProblemLanguageResultExecution timeMemory
979692vjudge1Painting Walls (APIO20_paint)C++17
0 / 100
1538 ms4444 KiB
#include <bits/stdc++.h> #include "paint.h" using namespace std; using ll = long long; const int N1 = 20200; const int M1 = 2020; int n, m; int g[N1][M1]; int f[N1][M1]; void precalc() { for (int j = 0; j < m; j++) { int x = n - 1, y = j; while (g[x][y] && f[n - 1][j] < m) { f[n - 1][j]++; x = (x + 1) % n; y = (y + 1) % m; } } for (int i = n - 2; i >= 0; i--) { for (int j = 0; j < m; j++) { if (g[i][j]) f[i][j] = 1 + f[i + 1][(j + 1) % m]; else f[i][j] = 0; } } } const int N = 100100; int to[N][18]; int dt[N][18]; bool able[N] = {}; int minimumInstructions( int N, int M, int K, vector<int> C, vector<int> A, vector<vector<int>> B) { n = N, m = M; if (n < N1 && m < M1) { for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { int x = lower_bound(B[j].begin(), B[j].end(), C[i]) - B[j].begin(); g[i][j] = (x != A[j] && B[j][x] == C[i]); } } precalc(); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) able[i] |= (f[i][j] >= m); } } else { bool used[K + 1] = {}; for (int i = 0; i < m; i++) { for (int j = 0; j < A[i]; j++) { used[B[i][j]] = true; } } int cnt = 0; map<int, int> mp; for (int i = 0; i < m; i++) { mp[C[i]]++; cnt += used[i]; } for (int i = 0; i < n; i++) { able[i] = ((int)mp.size() == m && cnt == m); cnt -= used[C[i]]; cnt += used[C[(i + m) % n]]; mp[C[i]]--; mp[C[(i + m) % n]]++; if (!mp[C[i]]) mp.erase(C[i]); } } { if (!able[0]) return -1; if (m == n) return 1; int nxt = 0, w = 0; for (int i = 0; i <= n - m; i++) { if (able[i]) { nxt = (i + m); w = 0; } if (w >= m) nxt = i; to[i][0] = nxt; dt[i][0] = (nxt - i); w++; } } for (int k = 1; k < 18; k++) { for (int i = 0; i < n; i++) { to[i][k] = to[to[i][k - 1]][k - 1]; dt[i][k] = dt[i][k - 1] + dt[to[i][k - 1]][k - 1]; } } int res = 1e9; int x = 0, ans = 0; while (x < n && to[x][0] != x) { ans++; x = to[x][0]; } if (x == n) return ans; return -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:108:9: warning: unused variable 'res' [-Wunused-variable]
  108 |     int res = 1e9;
      |         ^~~
#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...