Submission #647919

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
647919	2022-10-04T15:55:42 Z	rainboy	Broken Device 2 (JOI22_device2)	C++17	13 / 100	2000 ms	25924 KB

Anna

/* https://www.ioi-jp.org/camp/2022/2022-sp-tasks/contest3/device2-review.pdf */
#include "Anna.h"
#include <vector>

using namespace std;

const int L = 2000;

typedef vector<int> vi;

namespace {
	int f(int l) {
		if (l == 1)
			return 3;
		if (l == 2)
			return 6;
		return (l * 2 - 3) * 4;
	}

	int g(int l, int k) {
		int n = 0;
		if (k >= 4)
			n++;
		if (l * 2 - k >= 4)
			n++;
		if (k >= 2 && l * 2 - k >= 2)
			n += 2;
		if (n == 0)
			n = 1;
		return n;
	}
}

int Declare() {
	return L;
}

pair<vi, vi> Anna(long long x) {
	x--;
	int l = 1;
	while (x >= f(l))
		x -= f(l++);
	int k = 0;
	while (x >= g(l, k))
		x -= g(l, k++);
	vi aa(l, 0), bb(l, 0);
	if (k >= 4 && x-- == 0) {
		aa[0] = bb[0] = 1;
		aa[l - 1] = bb[l - 1] = 1;
		if (k <= l + 2)
			for (int i = 1; i <= k - 4; i++)
				aa[i] = 1;
		else {
			for (int i = 1; i <= l - 2; i++)
				aa[i] = 1;
			for (int i = 1; i <= k - l - 2; i++)
				bb[i] = 1;
		}
	} else if (l * 2 - k >= 4 && x-- == 0) {
		aa[0] = bb[0] = 0;
		aa[l - 1] = bb[l - 1] = 0;
		if (k <= l - 2)
			for (int i = 1; i <= k; i++)
				aa[i] = 1;
		else {
			for (int i = 1; i <= l - 2; i++)
				aa[i] = 1;
			for (int i = 1; i <= k - l + 2; i++)
				bb[i] = 1;
		}
	} else if (k >= 2 && l * 2 - k >= 2 && x-- == 0) {
		aa[0] = bb[0] = 0;
		aa[l - 1] = bb[l - 1] = 1;
		if (k <= l)
			for (int i = 1; i <= k - 2; i++)
				aa[i] = 1;
		else {
			for (int i = 1; i <= l - 2; i++)
				aa[i] = 1;
			for (int i = 1; i <= k - l; i++)
				bb[i] = 1;
		}
	} else if (k >= 2 && l * 2 - k >= 2 && x-- == 0) {
		aa[0] = bb[0] = 1;
		aa[l - 1] = bb[l - 1] = 0;
		if (k <= l)
			for (int i = 1; i <= k - 2; i++)
				aa[i] = 1;
		else {
			for (int i = 1; i <= l - 2; i++)
				aa[i] = 1;
			for (int i = 1; i <= k - l; i++)
				bb[i] = 1;
		}
	} else {
		if (k <= l)
			for (int i = 0; i < k; i++)
				aa[i] = 1;
		else {
			for (int i = 0; i < l; i++)
				aa[i] = 1;
			for (int i = 0; i < k - l; i++)
				bb[i] = 1;
		}
	}
	return make_pair(aa, bb);
}

Bruno

/* https://www.ioi-jp.org/camp/2022/2022-sp-tasks/contest3/device2-review.pdf */
#include "Bruno.h"
#include <vector>

using namespace std;

typedef vector<int> vi;

namespace {
	int f(int l) {
		if (l == 1)
			return 3;
		if (l == 2)
			return 6;
		return (l * 2 - 3) * 4;
	}

	int g(int l, int k) {
		int n = 0;
		if (k >= 4)
			n++;
		if (l * 2 - k >= 4)
			n++;
		if (k >= 2 && l * 2 - k >= 2)
			n += 2;
		if (n == 0)
			n = 1;
		return n;
	}
}

long long Bruno(vi cc) {
	int l = cc.size() / 2, k = 0;
	for (int i = 0; i < l * 2; i++)
		if (cc[i] == 1)
			k++;
	int x = 1;
	for (int l_ = 1; l_ < l; l_++)
		x += f(l_);
	for (int k_ = 0; k_ < k; k_++)
		x += g(l, k_);
	if (g(l, k) > 1) {
		if (cc[0] == 1 && cc[l * 2 - 1] == 1)
			return x;
		if (k >= 4)
			x++;
		if (cc[0] == 0 && cc[l * 2 - 1] == 0)
			return x;
		if (l * 2 - k >= 4)
			x++;
		if (cc[0] == 0 && cc[l * 2 - 1] == 1)
			return x;
		if (k >= 2 && l * 2 - k >= 2)
			x++;
	}
	return x;
}

Subtask #1

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	512 KB	Output is correct
2	Correct	12 ms	824 KB	Output is correct
3	Correct	17 ms	884 KB	Output is correct

Subtask #2

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	512 KB	Output is correct
2	Correct	12 ms	824 KB	Output is correct
3	Correct	17 ms	884 KB	Output is correct
4	Correct	275 ms	11548 KB	Output is correct
5	Correct	253 ms	11356 KB	Output is correct
6	Correct	298 ms	11528 KB	Output is correct
7	Correct	272 ms	11116 KB	Output is correct
8	Correct	276 ms	11520 KB	Output is correct
9	Correct	396 ms	16472 KB	Output is correct
10	Correct	394 ms	16412 KB	Output is correct

Subtask #3

3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	512 KB	Output is correct
2	Correct	12 ms	824 KB	Output is correct
3	Correct	17 ms	884 KB	Output is correct
4	Correct	275 ms	11548 KB	Output is correct
5	Correct	253 ms	11356 KB	Output is correct
6	Correct	298 ms	11528 KB	Output is correct
7	Correct	272 ms	11116 KB	Output is correct
8	Correct	276 ms	11520 KB	Output is correct
9	Correct	396 ms	16472 KB	Output is correct
10	Correct	394 ms	16412 KB	Output is correct
11	Correct	434 ms	17820 KB	Output is correct
12	Correct	439 ms	17748 KB	Output is correct
13	Correct	463 ms	17612 KB	Output is correct
14	Correct	413 ms	17464 KB	Output is correct
15	Correct	429 ms	17344 KB	Output is correct
16	Correct	581 ms	25924 KB	Output is correct
17	Correct	596 ms	25668 KB	Output is correct
18	Correct	305 ms	13068 KB	Output is correct
19	Correct	325 ms	13328 KB	Output is correct
20	Correct	300 ms	12768 KB	Output is correct

Subtask #4

0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	512 KB	Output is correct
2	Correct	12 ms	824 KB	Output is correct
3	Correct	17 ms	884 KB	Output is correct
4	Correct	275 ms	11548 KB	Output is correct
5	Correct	253 ms	11356 KB	Output is correct
6	Correct	298 ms	11528 KB	Output is correct
7	Correct	272 ms	11116 KB	Output is correct
8	Correct	276 ms	11520 KB	Output is correct
9	Correct	396 ms	16472 KB	Output is correct
10	Correct	394 ms	16412 KB	Output is correct
11	Correct	434 ms	17820 KB	Output is correct
12	Correct	439 ms	17748 KB	Output is correct
13	Correct	463 ms	17612 KB	Output is correct
14	Correct	413 ms	17464 KB	Output is correct
15	Correct	429 ms	17344 KB	Output is correct
16	Correct	581 ms	25924 KB	Output is correct
17	Correct	596 ms	25668 KB	Output is correct
18	Correct	305 ms	13068 KB	Output is correct
19	Correct	325 ms	13328 KB	Output is correct
20	Correct	300 ms	12768 KB	Output is correct
21	Incorrect	1 ms	620 KB	Wrong Answer [3]
22	Halted	0 ms	0 KB	-

Subtask #5

0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	512 KB	Output is correct
2	Correct	12 ms	824 KB	Output is correct
3	Correct	17 ms	884 KB	Output is correct
4	Correct	275 ms	11548 KB	Output is correct
5	Correct	253 ms	11356 KB	Output is correct
6	Correct	298 ms	11528 KB	Output is correct
7	Correct	272 ms	11116 KB	Output is correct
8	Correct	276 ms	11520 KB	Output is correct
9	Correct	396 ms	16472 KB	Output is correct
10	Correct	394 ms	16412 KB	Output is correct
11	Correct	434 ms	17820 KB	Output is correct
12	Correct	439 ms	17748 KB	Output is correct
13	Correct	463 ms	17612 KB	Output is correct
14	Correct	413 ms	17464 KB	Output is correct
15	Correct	429 ms	17344 KB	Output is correct
16	Correct	581 ms	25924 KB	Output is correct
17	Correct	596 ms	25668 KB	Output is correct
18	Correct	305 ms	13068 KB	Output is correct
19	Correct	325 ms	13328 KB	Output is correct
20	Correct	300 ms	12768 KB	Output is correct
21	Incorrect	1 ms	620 KB	Wrong Answer [3]
22	Halted	0 ms	0 KB	-

Subtask #6

0 / 60.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	2091 ms	212 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-