Submission #365663

#	Time	Username	Problem	Language	Result	Execution time	Memory
365663		sean617	Painting Walls (APIO20_paint)	C++17	100 / 100	1098 ms	22144 KiB

paint

#include "paint.h"
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#define N 100005

using namespace std;
vector<int> co[N], a[300000], a1, a2;
int v[N], s[N];
bool po[N];
int minimumInstructions(int n, int m, int l, vector<int> c, vector<int> sz, vector<std::vector<int>> b) {
	int i, ii, ans, j, t, t2, z;
	for (i = 0; i < m; i++) {
		for (j = 0; j < sz[i]; j++) {
			co[b[i][j]].push_back(i);
//			v[b[i][j]].insert(i);
		}
	}
	memset(v, -1, sizeof(v));
	for (i = 0; i < co[c[0]].size(); i++) {
		v[co[c[0]][i]] = 0;
		s[co[c[0]][i]] = 1;
		if (m == 1) po[0] = 1;
	}
	for (i = 1; i < n; i++) {
		t = c[i];
		a1.clear();
		a2.clear();
		for (j = 0; j < co[t].size(); j++) {
			t2 = (co[t][j] - 1 + m) % m;
			a1.push_back((t2 + 1) % m);
			if (v[t2] == i - 1) {
				a2.push_back(s[t2] + 1);
			} else {
				a2.push_back(1);
			}
		}
		for (j = 0; j < a1.size(); j++) {
			v[a1[j]] = i;
			s[a1[j]] = a2[j];
			if (a2[j] >= m) {
				po[i - m + 1] = 1;
			}
		}
	}
	if (!po[0]) return -1;
	i = m;
	j = 0;
	ans = 1;
	while (i < n) {
		ii = -1;
		for (; j <= i; j++) {
			if (po[j]) ii = j + m;
		}
		if (ii == -1) return -1;
		i = ii;
		ans++;
	}
	return ans;
//	for (k = 1; k < m; k *= 2);
//	for (i = 0; i < m; i++) {
//		for (j = 0; j < co[c[i]].size(); j++) {
//			t = co[c[i]][j];
//			a[k + i].push_back(t);
//		}
//	}
//	for (i = k - 1; i >= 1; i--) {
//
//	}
}

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:21:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |  for (i = 0; i < co[c[0]].size(); i++) {
      |              ~~^~~~~~~~~~~~~~~~~
paint.cpp:30:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |   for (j = 0; j < co[t].size(); j++) {
      |               ~~^~~~~~~~~~~~~~
paint.cpp:39:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |   for (j = 0; j < a1.size(); j++) {
      |               ~~^~~~~~~~~~~
paint.cpp:13:28: warning: unused variable 'z' [-Wunused-variable]
   13 |  int i, ii, ans, j, t, t2, z;
      |                            ^

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