답안 #598557

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
598557	2022-07-18T13:50:41 Z	piOOE	Rope (JOI17_rope)	C++17	15 / 100	2433 ms	468 KB

rope

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

void merge(vector<int> &a, vector<int> &b) {
  if (a.size() < b.size()) {
    swap(a, b);
  }
  for (int x: b) {
    a.push_back(x);
  }
  b.clear();
}

const int N = 15;

int a[N], ans[N];

int s, n, m;

void rec(int L, int R, vector<vector<int>> g) {
  if (L == s && R == s + 1) {
    for (int c1 = 0; c1 < m; ++c1) {
      for (int c2 = 0; c2 < m; ++c2) {
        int now = 0;
        for (int x: g[s]) {
          now += a[x] != c1;
        }
        for (int x: g[s + 1]) {
          now += a[x] != c2;
        }
        ans[c1] = min(ans[c1], now);
        ans[c2] = min(ans[c2], now);
      }
    }
    return;
  }
  for (int i = L + 1; i <= s; ++i) {
    if (i + (i - L) - 1 > R) {
      break;
    }
    vector nxt(g);
    for (int j = L; j < i; ++j) {
      merge(nxt[i + (i - j) - 1], nxt[j]);
    }
    rec(i, R, nxt);
  }
  for (int i = R - 1; i >= s + 1; --i) {
    if (i - (R - i) + 1 < s) {
      break;
    }
    vector nxt(g);
    for (int j = R; j > i; --j) {
      merge(nxt[i - (j - i) + 1], nxt[j]);
    }
    rec(L, i, nxt);
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  memset(ans, 0x3f, sizeof(ans));
  cin >> n >> m;
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
    --a[i];
  }
  vector g(n, vector<int>(1));
  for (int i = 0; i < n; ++i) {
    g[i][0] = i;
  }
  for (s = 0; s < n - 1; ++s) {
    rec(0, n - 1, g);
  }
  for (int i = 0; i < m; ++i) {
    cout << ans[i] << "\n";
  }
  return 0;
}

Subtask #1

15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2433 ms	324 KB	Output is correct
2	Correct	78 ms	320 KB	Output is correct
3	Correct	249 ms	212 KB	Output is correct
4	Correct	1301 ms	320 KB	Output is correct
5	Correct	404 ms	312 KB	Output is correct
6	Correct	257 ms	212 KB	Output is correct
7	Correct	664 ms	320 KB	Output is correct
8	Correct	1703 ms	324 KB	Output is correct
9	Correct	1633 ms	324 KB	Output is correct
10	Correct	1434 ms	340 KB	Output is correct
11	Correct	11 ms	212 KB	Output is correct
12	Correct	8 ms	320 KB	Output is correct
13	Correct	7 ms	340 KB	Output is correct
14	Correct	2 ms	212 KB	Output is correct
15	Correct	2 ms	328 KB	Output is correct
16	Correct	5 ms	340 KB	Output is correct
17	Correct	10 ms	320 KB	Output is correct
18	Correct	7 ms	324 KB	Output is correct
19	Correct	6 ms	212 KB	Output is correct
20	Correct	5 ms	212 KB	Output is correct
21	Correct	1 ms	212 KB	Output is correct
22	Correct	0 ms	212 KB	Output is correct
23	Correct	0 ms	324 KB	Output is correct
24	Correct	1 ms	324 KB	Output is correct
25	Correct	1 ms	212 KB	Output is correct
26	Correct	1 ms	212 KB	Output is correct

Subtask #2

0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2433 ms	324 KB	Output is correct
2	Correct	78 ms	320 KB	Output is correct
3	Correct	249 ms	212 KB	Output is correct
4	Correct	1301 ms	320 KB	Output is correct
5	Correct	404 ms	312 KB	Output is correct
6	Correct	257 ms	212 KB	Output is correct
7	Correct	664 ms	320 KB	Output is correct
8	Correct	1703 ms	324 KB	Output is correct
9	Correct	1633 ms	324 KB	Output is correct
10	Correct	1434 ms	340 KB	Output is correct
11	Correct	11 ms	212 KB	Output is correct
12	Correct	8 ms	320 KB	Output is correct
13	Correct	7 ms	340 KB	Output is correct
14	Correct	2 ms	212 KB	Output is correct
15	Correct	2 ms	328 KB	Output is correct
16	Correct	5 ms	340 KB	Output is correct
17	Correct	10 ms	320 KB	Output is correct
18	Correct	7 ms	324 KB	Output is correct
19	Correct	6 ms	212 KB	Output is correct
20	Correct	5 ms	212 KB	Output is correct
21	Correct	1 ms	212 KB	Output is correct
22	Correct	0 ms	212 KB	Output is correct
23	Correct	0 ms	324 KB	Output is correct
24	Correct	1 ms	324 KB	Output is correct
25	Correct	1 ms	212 KB	Output is correct
26	Correct	1 ms	212 KB	Output is correct
27	Runtime error	1 ms	468 KB	Execution killed with signal 11
28	Halted	0 ms	0 KB	-

Subtask #3

0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2433 ms	324 KB	Output is correct
2	Correct	78 ms	320 KB	Output is correct
3	Correct	249 ms	212 KB	Output is correct
4	Correct	1301 ms	320 KB	Output is correct
5	Correct	404 ms	312 KB	Output is correct
6	Correct	257 ms	212 KB	Output is correct
7	Correct	664 ms	320 KB	Output is correct
8	Correct	1703 ms	324 KB	Output is correct
9	Correct	1633 ms	324 KB	Output is correct
10	Correct	1434 ms	340 KB	Output is correct
11	Correct	11 ms	212 KB	Output is correct
12	Correct	8 ms	320 KB	Output is correct
13	Correct	7 ms	340 KB	Output is correct
14	Correct	2 ms	212 KB	Output is correct
15	Correct	2 ms	328 KB	Output is correct
16	Correct	5 ms	340 KB	Output is correct
17	Correct	10 ms	320 KB	Output is correct
18	Correct	7 ms	324 KB	Output is correct
19	Correct	6 ms	212 KB	Output is correct
20	Correct	5 ms	212 KB	Output is correct
21	Correct	1 ms	212 KB	Output is correct
22	Correct	0 ms	212 KB	Output is correct
23	Correct	0 ms	324 KB	Output is correct
24	Correct	1 ms	324 KB	Output is correct
25	Correct	1 ms	212 KB	Output is correct
26	Correct	1 ms	212 KB	Output is correct
27	Runtime error	1 ms	468 KB	Execution killed with signal 11
28	Halted	0 ms	0 KB	-

Subtask #4

0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2433 ms	324 KB	Output is correct
2	Correct	78 ms	320 KB	Output is correct
3	Correct	249 ms	212 KB	Output is correct
4	Correct	1301 ms	320 KB	Output is correct
5	Correct	404 ms	312 KB	Output is correct
6	Correct	257 ms	212 KB	Output is correct
7	Correct	664 ms	320 KB	Output is correct
8	Correct	1703 ms	324 KB	Output is correct
9	Correct	1633 ms	324 KB	Output is correct
10	Correct	1434 ms	340 KB	Output is correct
11	Correct	11 ms	212 KB	Output is correct
12	Correct	8 ms	320 KB	Output is correct
13	Correct	7 ms	340 KB	Output is correct
14	Correct	2 ms	212 KB	Output is correct
15	Correct	2 ms	328 KB	Output is correct
16	Correct	5 ms	340 KB	Output is correct
17	Correct	10 ms	320 KB	Output is correct
18	Correct	7 ms	324 KB	Output is correct
19	Correct	6 ms	212 KB	Output is correct
20	Correct	5 ms	212 KB	Output is correct
21	Correct	1 ms	212 KB	Output is correct
22	Correct	0 ms	212 KB	Output is correct
23	Correct	0 ms	324 KB	Output is correct
24	Correct	1 ms	324 KB	Output is correct
25	Correct	1 ms	212 KB	Output is correct
26	Correct	1 ms	212 KB	Output is correct
27	Runtime error	1 ms	468 KB	Execution killed with signal 11
28	Halted	0 ms	0 KB	-

Subtask #5

0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2433 ms	324 KB	Output is correct
2	Correct	78 ms	320 KB	Output is correct
3	Correct	249 ms	212 KB	Output is correct
4	Correct	1301 ms	320 KB	Output is correct
5	Correct	404 ms	312 KB	Output is correct
6	Correct	257 ms	212 KB	Output is correct
7	Correct	664 ms	320 KB	Output is correct
8	Correct	1703 ms	324 KB	Output is correct
9	Correct	1633 ms	324 KB	Output is correct
10	Correct	1434 ms	340 KB	Output is correct
11	Correct	11 ms	212 KB	Output is correct
12	Correct	8 ms	320 KB	Output is correct
13	Correct	7 ms	340 KB	Output is correct
14	Correct	2 ms	212 KB	Output is correct
15	Correct	2 ms	328 KB	Output is correct
16	Correct	5 ms	340 KB	Output is correct
17	Correct	10 ms	320 KB	Output is correct
18	Correct	7 ms	324 KB	Output is correct
19	Correct	6 ms	212 KB	Output is correct
20	Correct	5 ms	212 KB	Output is correct
21	Correct	1 ms	212 KB	Output is correct
22	Correct	0 ms	212 KB	Output is correct
23	Correct	0 ms	324 KB	Output is correct
24	Correct	1 ms	324 KB	Output is correct
25	Correct	1 ms	212 KB	Output is correct
26	Correct	1 ms	212 KB	Output is correct
27	Runtime error	1 ms	468 KB	Execution killed with signal 11
28	Halted	0 ms	0 KB	-