Submission #393250

#	Time	Username	Problem	Language	Result	Execution time	Memory
393250		anime	Painting Walls (APIO20_paint)	C++14	51 / 100	395 ms	196844 KiB

paint

//#include "grader.cpp"
#include "paint.h"
#include <bits/stdc++.h>
#define pb push_back
#define pii pair<int,int>
#define fr first
#define sc second
#define OK puts("OK");
#define endi puts("");
#define ret return
#define all(s) s.begin(),s.end()
using namespace std;
const int N = 1e5+5,INF = 1e9+7;
vector <int> v[N],c;
int n,m,k;
bitset <2000> can[N];
int p[N],dp[20000][2000];

bool is(int l,int r){
	int i,x = r-l+1;
	for (i=0;i<m;++i){
		if (l == 0){
			if (dp[r][i] == x)ret 1;
		}
		else {
			int y = dp[r][i]-dp[l-1][i];
			if (y == x)ret 1;
		}
	}
	ret 0;
}

int minimumInstructions(int N, int M, int K,vector<int> C,vector<int> A, vector<vector<int>> B){
	c = C;n=N;m=M;k=K;
	
    int i,j,ans=0;
    for (i=0;i<m;++i)
        for (int x: B[i])
			can[x][i] = 1;
	
	for (i=0;i<n;++i){
		if (i > 0)
			for (j=0;j<m;++j){
				int x = j-1;
				x+=m;
				x%=m;
				dp[i][j] = dp[i-1][x];
			}
		for (j=0;j<m;++j)
			if (can[c[i]][j] == 1)
				dp[i][j]++;
	}
	for (i=0;i<n-m+1;++i)
		p[i] = is(i,i+m-1);
	int pos = 0,z=1;
	while (pos >= 0 && pos < n && z>0){
		if (p[pos] == 1){
			pos +=m;
			ans++;
			z= m;
		}
		else {
			pos--;
			z--;
		}
	}
	if (pos < n)ans= -1;
	ret ans;


}

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:37:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   37 |     for (i=0;i<m;++i)
      |     ^~~
paint.cpp:41:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   41 |  for (i=0;i<n;++i){
      |  ^~~

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