Task: | Shakki |
Sender: | Henrik Lievonen |
Submission time: | 2015-12-04 20:20:20 +0200 |
Language: | C++ |
Status: | READY |
Result: | 0 |
group | verdict | score |
---|---|---|
#1 | TIME LIMIT EXCEEDED | 0 |
#2 | TIME LIMIT EXCEEDED | 0 |
#3 | TIME LIMIT EXCEEDED | 0 |
#4 | TIME LIMIT EXCEEDED | 0 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | TIME LIMIT EXCEEDED | -- | 1 | details |
#2 | TIME LIMIT EXCEEDED | -- | 1 | details |
#3 | TIME LIMIT EXCEEDED | -- | 1 | details |
#4 | TIME LIMIT EXCEEDED | -- | 1 | details |
#5 | TIME LIMIT EXCEEDED | -- | 1 | details |
#6 | TIME LIMIT EXCEEDED | -- | 1 | details |
#7 | TIME LIMIT EXCEEDED | -- | 1 | details |
#8 | TIME LIMIT EXCEEDED | -- | 1 | details |
#9 | TIME LIMIT EXCEEDED | -- | 1 | details |
#10 | TIME LIMIT EXCEEDED | -- | 1 | details |
#11 | TIME LIMIT EXCEEDED | -- | 2 | details |
#12 | TIME LIMIT EXCEEDED | -- | 2 | details |
#13 | TIME LIMIT EXCEEDED | -- | 2 | details |
#14 | TIME LIMIT EXCEEDED | -- | 2 | details |
#15 | TIME LIMIT EXCEEDED | -- | 2 | details |
#16 | TIME LIMIT EXCEEDED | -- | 2 | details |
#17 | TIME LIMIT EXCEEDED | -- | 2 | details |
#18 | TIME LIMIT EXCEEDED | -- | 2 | details |
#19 | TIME LIMIT EXCEEDED | -- | 2 | details |
#20 | TIME LIMIT EXCEEDED | -- | 2 | details |
#21 | TIME LIMIT EXCEEDED | -- | 3 | details |
#22 | TIME LIMIT EXCEEDED | -- | 3 | details |
#23 | TIME LIMIT EXCEEDED | -- | 3 | details |
#24 | TIME LIMIT EXCEEDED | -- | 3 | details |
#25 | TIME LIMIT EXCEEDED | -- | 3 | details |
#26 | TIME LIMIT EXCEEDED | -- | 3 | details |
#27 | TIME LIMIT EXCEEDED | -- | 3 | details |
#28 | TIME LIMIT EXCEEDED | -- | 3 | details |
#29 | TIME LIMIT EXCEEDED | -- | 3 | details |
#30 | TIME LIMIT EXCEEDED | -- | 3 | details |
#31 | TIME LIMIT EXCEEDED | -- | 4 | details |
#32 | TIME LIMIT EXCEEDED | -- | 4 | details |
#33 | TIME LIMIT EXCEEDED | -- | 4 | details |
#34 | TIME LIMIT EXCEEDED | -- | 4 | details |
#35 | TIME LIMIT EXCEEDED | -- | 4 | details |
#36 | TIME LIMIT EXCEEDED | -- | 4 | details |
#37 | TIME LIMIT EXCEEDED | -- | 4 | details |
#38 | TIME LIMIT EXCEEDED | -- | 4 | details |
#39 | TIME LIMIT EXCEEDED | -- | 4 | details |
#40 | TIME LIMIT EXCEEDED | -- | 4 | details |
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);elsethis->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: TIME LIMIT EXCEEDED
input |
---|
VMMVVMVV MMVVMVVV MMVVMMMM MVVVMVVM MVVVVMVM ... |
correct output |
---|
100000 |
user output |
---|
(empty) |
Test 2
Group: 1
Verdict: TIME LIMIT EXCEEDED
input |
---|
MVMVVMMV VVMMVVVV VMMVMMVM MVVVVMVM MVMVMMVM ... |
correct output |
---|
100000 |
user output |
---|
(empty) |
Test 3
Group: 1
Verdict: TIME LIMIT EXCEEDED
input |
---|
VMMMVMVV MMMVMVMV VMMVMVVM VVVMVMMV MVMVMVMV ... |
correct output |
---|
100000 |
user output |
---|
(empty) |
Test 4
Group: 1
Verdict: TIME LIMIT EXCEEDED
input |
---|
VVVMVMVV VMMVMVMM MVVMMVMV VMVMMVMM MMVVMMVM ... |
correct output |
---|
100000 |
user output |
---|
(empty) |
Test 5
Group: 1
Verdict: TIME LIMIT EXCEEDED
input |
---|
MVMVVMMM VVMMVVMV MVVMVVMM VMVMVMMV MMVMVVVM ... |
correct output |
---|
100000 |
user output |
---|
(empty) |
Test 6
Group: 1
Verdict: TIME LIMIT EXCEEDED
input |
---|
VMMVMVVM VVMMVVMM MMMVMVVM VMMVMMVM MVMVMMMV ... |
correct output |
---|
100000 |
user output |
---|
(empty) |
Test 7
Group: 1
Verdict: TIME LIMIT EXCEEDED
input |
---|
MVVVVMMM MMMMMMMM VVVVVMMV MMVVMVVM VMVVVVMV ... |
correct output |
---|
100000 |
user output |
---|
(empty) |
Test 8
Group: 1
Verdict: TIME LIMIT EXCEEDED
input |
---|
VMMVMVMM MMMVVMMM MVVVVVVV VVVVMMMV MVVVMVVM ... |
correct output |
---|
100000 |
user output |
---|
(empty) |
Test 9
Group: 1
Verdict: TIME LIMIT EXCEEDED
input |
---|
VVVVVMMM MMVVVVVV MVVVMMMM VVMVVVVM VMMVMVMM ... |
correct output |
---|
100000 |
user output |
---|
(empty) |
Test 10
Group: 1
Verdict: TIME LIMIT EXCEEDED
input |
---|
VMMVMMMM VVMVVVVV VMMVMVMV VMMVMVMM VVVMMMMM ... |
correct output |
---|
100000 |
user output |
---|
(empty) |
Test 11
Group: 2
Verdict: TIME LIMIT EXCEEDED
input |
---|
VMVMVVMM MMVMVVMM VMVVVMMV VVVMVMVM VVMMVVMM ... |
correct output |
---|
25000 |
user output |
---|
(empty) |
Test 12
Group: 2
Verdict: TIME LIMIT EXCEEDED
input |
---|
MVMVVMVV VMMVVMVM VMVVVMMM VMMMMVVM MMVVVMMM ... |
correct output |
---|
25000 |
user output |
---|
(empty) |
Test 13
Group: 2
Verdict: TIME LIMIT EXCEEDED
input |
---|
MVVMMVVV MMVVMVMM VVVMVMVV VMVMMMMM MVVMMVMV ... |
correct output |
---|
25000 |
user output |
---|
(empty) |
Test 14
Group: 2
Verdict: TIME LIMIT EXCEEDED
input |
---|
VVMMMVMV VMVVVMVV VVMVVVMM MVVMVMVM MMVVMMMM ... |
correct output |
---|
25000 |
user output |
---|
(empty) |
Test 15
Group: 2
Verdict: TIME LIMIT EXCEEDED
input |
---|
MVVVMVVV MMMMVMMM MVMMMVVM MMVVVMVM VMVVVMMV ... |
correct output |
---|
25000 |
user output |
---|
(empty) |
Test 16
Group: 2
Verdict: TIME LIMIT EXCEEDED
input |
---|
VMMVMVVM VMMVVVVV MVMVMMVM VMMVVVMV VVMVMMVM ... |
correct output |
---|
25000 |
user output |
---|
(empty) |
Test 17
Group: 2
Verdict: TIME LIMIT EXCEEDED
input |
---|
MVVMMVVM MVVVMMMV MVVMMVVM VMMVMVMV VMMVMMMM ... |
correct output |
---|
25000 |
user output |
---|
(empty) |
Test 18
Group: 2
Verdict: TIME LIMIT EXCEEDED
input |
---|
MVMMVVMM VVMMMMVV VMVVVVVM MVMMMVMV VMVVVMVM ... |
correct output |
---|
25000 |
user output |
---|
(empty) |
Test 19
Group: 2
Verdict: TIME LIMIT EXCEEDED
input |
---|
MVVVVVVV VMMVMVVM VMVMMMMV MVMVMMMM MMVVVMMM ... |
correct output |
---|
25000 |
user output |
---|
(empty) |
Test 20
Group: 2
Verdict: TIME LIMIT EXCEEDED
input |
---|
MVVVMMMM MMVMMVMV MVVVVVMM VVMMMVVM VVVMVMVV ... |
correct output |
---|
25000 |
user output |
---|
(empty) |
Test 21
Group: 3
Verdict: TIME LIMIT EXCEEDED
input |
---|
VMVVMVMM MMMMVMMV VVVMVVVV MVMVMVVM VMMVMMMM ... |
correct output |
---|
5000 |
user output |
---|
(empty) |
Test 22
Group: 3
Verdict: TIME LIMIT EXCEEDED
input |
---|
VVVVVVMM MMMVMMVV VVVVVVMV MMMVMVVV MVVMMMMV ... |
correct output |
---|
5000 |
user output |
---|
(empty) |
Test 23
Group: 3
Verdict: TIME LIMIT EXCEEDED
input |
---|
MMVMVMVV MMVVMVVM VMMVVMVM MMMMMMVV MVVVVMVM ... |
correct output |
---|
5000 |
user output |
---|
(empty) |
Test 24
Group: 3
Verdict: TIME LIMIT EXCEEDED
input |
---|
MVMVVMVM VVMVVMVM MMMMVMVV MVVMMVVV MMMMMVVV ... |
correct output |
---|
5000 |
user output |
---|
(empty) |
Test 25
Group: 3
Verdict: TIME LIMIT EXCEEDED
input |
---|
MVVVMVVM MMMMVVMV VMMVMMVV VVMVMVMV MVMMMVMM ... |
correct output |
---|
5000 |
user output |
---|
(empty) |
Test 26
Group: 3
Verdict: TIME LIMIT EXCEEDED
input |
---|
VMVMVVVM MMMVVVMM MMVVVVVM VVVVMMVV VMMVVMMV ... |
correct output |
---|
5000 |
user output |
---|
(empty) |
Test 27
Group: 3
Verdict: TIME LIMIT EXCEEDED
input |
---|
MMVMMVVM MVVVMVMV MVVVMVVM VMVMMMVV VMMVVVVV ... |
correct output |
---|
5000 |
user output |
---|
(empty) |
Test 28
Group: 3
Verdict: TIME LIMIT EXCEEDED
input |
---|
MVMMVMMV VMVMMMVV MMMMVVMV VVVVMMMM MMMVMMVV ... |
correct output |
---|
5000 |
user output |
---|
(empty) |
Test 29
Group: 3
Verdict: TIME LIMIT EXCEEDED
input |
---|
VVVVMVMV MMMVVMVM MVVVMVMV VVVMVVMM VMMMMMVV ... |
correct output |
---|
5000 |
user output |
---|
(empty) |
Test 30
Group: 3
Verdict: TIME LIMIT EXCEEDED
input |
---|
MVVVMVVV MMVVMMMM MVVVVVVV MVMVMMMV VMMMVMMM ... |
correct output |
---|
5000 |
user output |
---|
(empty) |
Test 31
Group: 4
Verdict: TIME LIMIT EXCEEDED
input |
---|
MVMMVMMV VVVMMVVV VMMVVMMV VVMMMVVM VVVMMMVV ... |
correct output |
---|
250 |
user output |
---|
(empty) |
Test 32
Group: 4
Verdict: TIME LIMIT EXCEEDED
input |
---|
VVMMVVVM VMVVMMVV VMMMMMMV VVMVMVVV VMMVMVMM ... |
correct output |
---|
250 |
user output |
---|
(empty) |
Test 33
Group: 4
Verdict: TIME LIMIT EXCEEDED
input |
---|
MMVVMVMV VVVMVMMM VVVVMVMM MVVMVVMV VMMVMVVM ... |
correct output |
---|
250 |
user output |
---|
(empty) |
Test 34
Group: 4
Verdict: TIME LIMIT EXCEEDED
input |
---|
VMVMVVMV MVVMMMMM MMVVMMMM VMVMVVVM VMMMVVVM ... |
correct output |
---|
250 |
user output |
---|
(empty) |
Test 35
Group: 4
Verdict: TIME LIMIT EXCEEDED
input |
---|
VMVMVMMM VMMVVVMM MMVMVMMM MVMMVVVV VMMVMMMV ... |
correct output |
---|
250 |
user output |
---|
(empty) |
Test 36
Group: 4
Verdict: TIME LIMIT EXCEEDED
input |
---|
MVMVMVMM MVMVMMMV MMVVVVMM MVMVVVVV VMMMVVMM ... |
correct output |
---|
250 |
user output |
---|
(empty) |
Test 37
Group: 4
Verdict: TIME LIMIT EXCEEDED
input |
---|
VMMMMVMM VVMMMVMV VMVVVVVV MVMMMVVM VMVMMVVM ... |
correct output |
---|
250 |
user output |
---|
(empty) |
Test 38
Group: 4
Verdict: TIME LIMIT EXCEEDED
input |
---|
VMMVMVMV VVMVMVMM MMMVMVMM MVVVVMMM MMVVVMVV ... |
correct output |
---|
250 |
user output |
---|
(empty) |
Test 39
Group: 4
Verdict: TIME LIMIT EXCEEDED
input |
---|
MMMMMVMV MVVMMMMV VMVVVVMM VMVVVMMV MVMMMVMM ... |
correct output |
---|
250 |
user output |
---|
(empty) |
Test 40
Group: 4
Verdict: TIME LIMIT EXCEEDED
input |
---|
VMMMMMMV VMMVVVVV MVMMVMMV MVVVVMMV MVVVVMMM ... |
correct output |
---|
250 |
user output |
---|
(empty) |