CSES - Putka Open 2015 – 6/6 - Results
Submission details
Task:Shakki
Sender:Henrik Lievonen
Submission time:2015-12-04 20:20:20 +0200
Language:C++
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
#40
Test results
testverdicttimegroup
#1--1details
#2--1details
#3--1details
#4--1details
#5--1details
#6--1details
#7--1details
#8--1details
#9--1details
#10--1details
#11--2details
#12--2details
#13--2details
#14--2details
#15--2details
#16--2details
#17--2details
#18--2details
#19--2details
#20--2details
#21--3details
#22--3details
#23--3details
#24--3details
#25--3details
#26--3details
#27--3details
#28--3details
#29--3details
#30--3details
#31--4details
#32--4details
#33--4details
#34--4details
#35--4details
#36--4details
#37--4details
#38--4details
#39--4details
#40--4details

Code

#include <iostream>
#include <cstdint>
#include <array>
#include <string>
#include <vector>
#include <random>

using namespace std;

mt19937 rnd(0);

class lauta {
	uint64_t state;
public:
	lauta(uint64_t state): state(state ){}
	lauta(array<array<char, 8>, 8> state) {
		this->state = 0;
		for (int x = 0; x < 8; x++)
			for (int y = 0; y < 8; y++)
				if (state[x][y] == 'M')
					this->state |= uint64_t(1) << indeksi(x, y);
	}

	lauta pyorita(const int x, const int y) {
		lauta uusi = *this;
		uusi.aseta(x, y, lue(x, y + 1));
		uusi.aseta(x + 1, y, lue(x, y));
		uusi.aseta(x + 1, y + 1, lue(x + 1, y));
		uusi.aseta(x, y + 1, lue(x + 1, y + 1));
		return uusi;
	}

	void aseta(const int x, const int y, const bool v) {
		int i = indeksi(x, y);
		if (v)
			this->state |= (uint64_t(1) << i);
		else
			this->state &= ~(uint64_t(1) << i);
	}
	bool lue(const int x,const  int y) const {
		int i = indeksi(x, y);
		return this->state & (uint64_t(1) << i);
	}

private:
	int indeksi(const int x,const  int y) const {
		return 8 * x + y;
	}
};

bool onkovalmis(const lauta &l) {
	for (int i = 1; i < 8; i++) {
		for (int j = 1; j < 8; j++) {
			if (l.lue(i, j) == l.lue(i, j - 1) || l.lue(i, j) == l.lue(i - 1, j))
				return false;
		}
	}
	return true;
}
int laskeoikeat(const lauta &l) {
	int r = 0;
	for (int i = 0; i < 8; i++) {
		for (int j = 0; j < 8; j++) {
			r += l.lue(i, j) == (i + j) % 2;
		}
	}
	return r;
}

int main() {
	cin.sync_with_stdio(false);
	cin.tie(nullptr);

	array<array<char, 8>, 8> state;
	for (int i = 0; i < 8; i++) {
		string s;
		cin >> s;
		for (int j = 0; j < 8; j++)
			state[i][j] = s[j];
	}

	lauta l(state);
	bool kasvata = laskeoikeat(l) > 32;

	vector<pair<int, int>> res;

	while (!onkovalmis(l)) {
		int nyt = laskeoikeat(l);
		vector<pair<int, int>> vaihtoehdot;
		lauta l2(0);
		pair<int, int> v;

		for (int i = 0; i < 7; i++) {
			for (int j = 0; j < 7; j++) {
				lauta l2 = l.pyorita(i, j);
				if (kasvata) {
					if (laskeoikeat(l2) > nyt) {
						res.push_back(make_pair(i, j));
						l = l2;
						goto next;
					}
				}
				else {
					if (laskeoikeat(l2) < nyt) {
						res.push_back(make_pair(i, j));
						l = l2;
						goto next;
					}
				}
			}
		}


		for (int i = 0; i < 7; i++) {
			for (int j = 0; j < 7; j++) {
				lauta l2 = l.pyorita(i, j);
				if (laskeoikeat(l2) == nyt) {
					vaihtoehdot.push_back(make_pair(i, j));
				}
			}
		}

		if (!vaihtoehdot.size()) {
			for (int i = 0; i < 7; i++) {
				for (int j = 0; j < 7; j++) {
					vaihtoehdot.push_back(make_pair(i, j));
				}
			}
		}

		v = vaihtoehdot[rnd() % vaihtoehdot.size()];
		l2 = l.pyorita(v.first, v.second);
		l = l2;
		res.push_back(v);

	next:;
	}

	cout << res.size() << '\n';
	for (auto r : res) {
		cout << r.first + 1 << " " << r.second + 1 << "\n";
	}
}

Test details

Test 1

Group: 1

Verdict:

input
VMMVVMVV
MMVVMVVV
MMVVMMMM
MVVVMVVM
MVVVVMVM
...

correct output
100000

user output
(empty)

Test 2

Group: 1

Verdict:

input
MVMVVMMV
VVMMVVVV
VMMVMMVM
MVVVVMVM
MVMVMMVM
...

correct output
100000

user output
(empty)

Test 3

Group: 1

Verdict:

input
VMMMVMVV
MMMVMVMV
VMMVMVVM
VVVMVMMV
MVMVMVMV
...

correct output
100000

user output
(empty)

Test 4

Group: 1

Verdict:

input
VVVMVMVV
VMMVMVMM
MVVMMVMV
VMVMMVMM
MMVVMMVM
...

correct output
100000

user output
(empty)

Test 5

Group: 1

Verdict:

input
MVMVVMMM
VVMMVVMV
MVVMVVMM
VMVMVMMV
MMVMVVVM
...

correct output
100000

user output
(empty)

Test 6

Group: 1

Verdict:

input
VMMVMVVM
VVMMVVMM
MMMVMVVM
VMMVMMVM
MVMVMMMV
...

correct output
100000

user output
(empty)

Test 7

Group: 1

Verdict:

input
MVVVVMMM
MMMMMMMM
VVVVVMMV
MMVVMVVM
VMVVVVMV
...

correct output
100000

user output
(empty)

Test 8

Group: 1

Verdict:

input
VMMVMVMM
MMMVVMMM
MVVVVVVV
VVVVMMMV
MVVVMVVM
...

correct output
100000

user output
(empty)

Test 9

Group: 1

Verdict:

input
VVVVVMMM
MMVVVVVV
MVVVMMMM
VVMVVVVM
VMMVMVMM
...

correct output
100000

user output
(empty)

Test 10

Group: 1

Verdict:

input
VMMVMMMM
VVMVVVVV
VMMVMVMV
VMMVMVMM
VVVMMMMM
...

correct output
100000

user output
(empty)

Test 11

Group: 2

Verdict:

input
VMVMVVMM
MMVMVVMM
VMVVVMMV
VVVMVMVM
VVMMVVMM
...

correct output
25000

user output
(empty)

Test 12

Group: 2

Verdict:

input
MVMVVMVV
VMMVVMVM
VMVVVMMM
VMMMMVVM
MMVVVMMM
...

correct output
25000

user output
(empty)

Test 13

Group: 2

Verdict:

input
MVVMMVVV
MMVVMVMM
VVVMVMVV
VMVMMMMM
MVVMMVMV
...

correct output
25000

user output
(empty)

Test 14

Group: 2

Verdict:

input
VVMMMVMV
VMVVVMVV
VVMVVVMM
MVVMVMVM
MMVVMMMM
...

correct output
25000

user output
(empty)

Test 15

Group: 2

Verdict:

input
MVVVMVVV
MMMMVMMM
MVMMMVVM
MMVVVMVM
VMVVVMMV
...

correct output
25000

user output
(empty)

Test 16

Group: 2

Verdict:

input
VMMVMVVM
VMMVVVVV
MVMVMMVM
VMMVVVMV
VVMVMMVM
...

correct output
25000

user output
(empty)

Test 17

Group: 2

Verdict:

input
MVVMMVVM
MVVVMMMV
MVVMMVVM
VMMVMVMV
VMMVMMMM
...

correct output
25000

user output
(empty)

Test 18

Group: 2

Verdict:

input
MVMMVVMM
VVMMMMVV
VMVVVVVM
MVMMMVMV
VMVVVMVM
...

correct output
25000

user output
(empty)

Test 19

Group: 2

Verdict:

input
MVVVVVVV
VMMVMVVM
VMVMMMMV
MVMVMMMM
MMVVVMMM
...

correct output
25000

user output
(empty)

Test 20

Group: 2

Verdict:

input
MVVVMMMM
MMVMMVMV
MVVVVVMM
VVMMMVVM
VVVMVMVV
...

correct output
25000

user output
(empty)

Test 21

Group: 3

Verdict:

input
VMVVMVMM
MMMMVMMV
VVVMVVVV
MVMVMVVM
VMMVMMMM
...

correct output
5000

user output
(empty)

Test 22

Group: 3

Verdict:

input
VVVVVVMM
MMMVMMVV
VVVVVVMV
MMMVMVVV
MVVMMMMV
...

correct output
5000

user output
(empty)

Test 23

Group: 3

Verdict:

input
MMVMVMVV
MMVVMVVM
VMMVVMVM
MMMMMMVV
MVVVVMVM
...

correct output
5000

user output
(empty)

Test 24

Group: 3

Verdict:

input
MVMVVMVM
VVMVVMVM
MMMMVMVV
MVVMMVVV
MMMMMVVV
...

correct output
5000

user output
(empty)

Test 25

Group: 3

Verdict:

input
MVVVMVVM
MMMMVVMV
VMMVMMVV
VVMVMVMV
MVMMMVMM
...

correct output
5000

user output
(empty)

Test 26

Group: 3

Verdict:

input
VMVMVVVM
MMMVVVMM
MMVVVVVM
VVVVMMVV
VMMVVMMV
...

correct output
5000

user output
(empty)

Test 27

Group: 3

Verdict:

input
MMVMMVVM
MVVVMVMV
MVVVMVVM
VMVMMMVV
VMMVVVVV
...

correct output
5000

user output
(empty)

Test 28

Group: 3

Verdict:

input
MVMMVMMV
VMVMMMVV
MMMMVVMV
VVVVMMMM
MMMVMMVV
...

correct output
5000

user output
(empty)

Test 29

Group: 3

Verdict:

input
VVVVMVMV
MMMVVMVM
MVVVMVMV
VVVMVVMM
VMMMMMVV
...

correct output
5000

user output
(empty)

Test 30

Group: 3

Verdict:

input
MVVVMVVV
MMVVMMMM
MVVVVVVV
MVMVMMMV
VMMMVMMM
...

correct output
5000

user output
(empty)

Test 31

Group: 4

Verdict:

input
MVMMVMMV
VVVMMVVV
VMMVVMMV
VVMMMVVM
VVVMMMVV
...

correct output
250

user output
(empty)

Test 32

Group: 4

Verdict:

input
VVMMVVVM
VMVVMMVV
VMMMMMMV
VVMVMVVV
VMMVMVMM
...

correct output
250

user output
(empty)

Test 33

Group: 4

Verdict:

input
MMVVMVMV
VVVMVMMM
VVVVMVMM
MVVMVVMV
VMMVMVVM
...

correct output
250

user output
(empty)

Test 34

Group: 4

Verdict:

input
VMVMVVMV
MVVMMMMM
MMVVMMMM
VMVMVVVM
VMMMVVVM
...

correct output
250

user output
(empty)

Test 35

Group: 4

Verdict:

input
VMVMVMMM
VMMVVVMM
MMVMVMMM
MVMMVVVV
VMMVMMMV
...

correct output
250

user output
(empty)

Test 36

Group: 4

Verdict:

input
MVMVMVMM
MVMVMMMV
MMVVVVMM
MVMVVVVV
VMMMVVMM
...

correct output
250

user output
(empty)

Test 37

Group: 4

Verdict:

input
VMMMMVMM
VVMMMVMV
VMVVVVVV
MVMMMVVM
VMVMMVVM
...

correct output
250

user output
(empty)

Test 38

Group: 4

Verdict:

input
VMMVMVMV
VVMVMVMM
MMMVMVMM
MVVVVMMM
MMVVVMVV
...

correct output
250

user output
(empty)

Test 39

Group: 4

Verdict:

input
MMMMMVMV
MVVMMMMV
VMVVVVMM
VMVVVMMV
MVMMMVMM
...

correct output
250

user output
(empty)

Test 40

Group: 4

Verdict:

input
VMMMMMMV
VMMVVVVV
MVMMVMMV
MVVVVMMV
MVVVVMMM
...

correct output
250

user output
(empty)