Submission #502792

#TimeUsernameProblemLanguageResultExecution timeMemory
502792VictorPainting Walls (APIO20_paint)C++17
28 / 100
1592 ms20656 KiB
// #pragma GCC target ("avx,avx2,fma") // #pragma GCC optimize ("Ofast,inline") // O1 - O2 - O3 - Os - Ofast // #pragma GCC optimize ("unroll-loops") #include "paint.h" #include <bits/stdc++.h> using namespace std; #define rep(i, a, b) for (int i = (a); i < (b); ++i) #define per(i, a, b) for (int i = (b - 1); i >= (a); --i) #define trav(a, x) for (auto &a : x) #define all(x) x.begin(), x.end() #define sz(x) x.size() #define pb push_back #define debug(x) cout << #x << " = " << x << endl #define umap unordered_map #define uset unordered_set typedef pair<int, int> ii; typedef pair<int, ii> iii; typedef vector<int> vi; typedef vector<ii> vii; typedef vector<vi> vvi; typedef long long ll; typedef pair<ll, ll> pll; typedef vector<ll> vll; typedef vector<pll> vpll; const int INF = 1'000'000'007; int n,m,k,jmp_back[100005]; vvi people; uset<int> colors[100005]; vi wall; vector<bool>possible; int minimumInstructions(int N, int M, int K, std::vector<int> C, std::vector<int> A, std::vector<std::vector<int>> B) { possible.assign(N,0); people.swap(B); wall.swap(C); n=N,m=M,k=K; rep(i,0,m) trav(color,people[i]) colors[color].insert(i); for(int pos=m-1;pos<n;pos+=m) { int cur_color=wall[pos]; assert(sz(colors[cur_color])<700); trav(person,colors[cur_color]) { int first_person=(person+1)%m,num_match=0; int start_pos=pos-m+1; rep(i,0,m-1) num_match+=colors[wall[start_pos+i]].count((first_person+i)%m); rep(i,m-1,m-1+(n-pos)){ num_match+=colors[wall[start_pos+m-1]].count((first_person-1+m)%m); if(num_match==m) possible[start_pos]=1; num_match-=colors[wall[start_pos]].count(first_person); first_person=(first_person+1)%m; ++start_pos; } } } int val=-INF; rep(i,0,n) { if(possible[i])val=i; jmp_back[i]=val; } //cout<<sz(possible)<<endl; int pos=0,ans=0; while(pos<n) { int nxt_pos=jmp_back[pos]; if(nxt_pos+m>pos) { pos=nxt_pos+m; ++ans; } else return -1; } return ans; } /* int main() { int N, M, K; assert(3 == scanf("%d %d %d", &N, &M, &K)); std::vector<int> C(N); for (int i = 0; i < N; ++i) { assert(1 == scanf("%d", &C[i])); } std::vector<int> A(M); std::vector<std::vector<int>> B(M); for (int i = 0; i < M; ++i) { assert(1 == scanf("%d", &A[i])); B[i].resize(A[i]); for (int j = 0; j < A[i]; ++j) { assert(1 == scanf("%d", &B[i][j])); } } int minimum_instructions = minimumInstructions(N, M, K, C, A, B); printf("%d\n", minimum_instructions); return 0; }*/
#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...