CSES - Putka Open 2015 – 6/6 - Results
Submission details
Task:Shakki
Sender:
Submission time:2015-12-04 21:52:02 +0200
Language:C++
Status:READY
Result:100
Feedback
groupverdictscore
#1ACCEPTED28
#2ACCEPTED21
#3ACCEPTED24
#4ACCEPTED27
Test results
testverdicttimegroup
#1ACCEPTED0.06 s1details
#2ACCEPTED0.07 s1details
#3ACCEPTED0.06 s1details
#4ACCEPTED0.05 s1details
#5ACCEPTED0.06 s1details
#6ACCEPTED0.05 s1details
#7ACCEPTED0.05 s1details
#8ACCEPTED0.06 s1details
#9ACCEPTED0.06 s1details
#10ACCEPTED0.06 s1details
#11ACCEPTED0.06 s2details
#12ACCEPTED0.06 s2details
#13ACCEPTED0.06 s2details
#14ACCEPTED0.06 s2details
#15ACCEPTED0.06 s2details
#16ACCEPTED0.06 s2details
#17ACCEPTED0.05 s2details
#18ACCEPTED0.05 s2details
#19ACCEPTED0.05 s2details
#20ACCEPTED0.06 s2details
#21ACCEPTED0.06 s3details
#22ACCEPTED0.05 s3details
#23ACCEPTED0.06 s3details
#24ACCEPTED0.05 s3details
#25ACCEPTED0.05 s3details
#26ACCEPTED0.06 s3details
#27ACCEPTED0.05 s3details
#28ACCEPTED0.05 s3details
#29ACCEPTED0.06 s3details
#30ACCEPTED0.06 s3details
#31ACCEPTED0.06 s4details
#32ACCEPTED0.05 s4details
#33ACCEPTED0.05 s4details
#34ACCEPTED0.06 s4details
#35ACCEPTED0.05 s4details
#36ACCEPTED0.06 s4details
#37ACCEPTED0.05 s4details
#38ACCEPTED0.05 s4details
#39ACCEPTED0.05 s4details
#40ACCEPTED0.05 s4details

Compiler report

input/code.cpp: In function 'unsigned int rot_4x4(unsigned int, int, int)':
input/code.cpp:28:23: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   auto n=b&~(0x33<<y*4+x);
                       ^
input/code.cpp:29:15: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   n|=(b&1<<y*4+x)<<1;
               ^
input/code.cpp:30:17: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   n|=(b&1<<y*4+x+1)<<4;
                 ^
input/code.cpp:31:19: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   n|=(b&1<<(y+1)*4+x)>>4;
                   ^
input/code.cpp:32:21: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   n|=(b&1<<(y+1)*4+x+1)>>1;
                     ^
input/code.cpp: In function 'std::vector<int> solve(std::vector<std::basic_string<char> >)':
input/code.cpp:87:44: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
       if(M[Y*4+y][X*4+x]=='M')block|=1<<y*4+x;...

Code

#include <algorithm>
#include <iostream>
#include <string>
#include <unordered_set>
#include <vector>
int rand7() {
static const std::string s(
"5015540611051231243566552452031661504340134160300563316012010431135015620614453361203302525024326505"
"2623155036566160535224424125015461313304246265065165356245006244540661040226431314252500050260115262"
"4101620532516146036314323665123532110665243521362516664055414325303423440040065613232106041205542621"
"2636143001406404503020215012242066553031202151033421142521414660612316446533514521034404121304153401"
"6351020103256141424211630505121645256225225334503516140352536455503634401463433124643246636015143366"
"3460443046460530554223025513331622613212443433013302213132350125614353531412350155656315030342253455"
"1631360205010562052142300015654503352321224516404112466056004426150556244502112046320632025236452366"
"0153203001513410221662432464136124446130253550433402112343252355611446234001262215032156136020103305"
"0234023052151142565523432541442663223212335156603212501614204122102513050545633654560303441361566116"
"5412134645331550404341564343313344511340151413022330010251356334136250142223131036040352024212104325");
static int i=0;
return s[i++%s.size()] - '0';
}
const unsigned P16=1<<16;
unsigned depth_4x4[P16];
unsigned yx_4x4[P16];
unsigned rot_4x4(unsigned b,int x,int y){
auto n=b&~(0x33<<y*4+x);
n|=(b&1<<y*4+x)<<1;
n|=(b&1<<y*4+x+1)<<4;
n|=(b&1<<(y+1)*4+x)>>4;
n|=(b&1<<(y+1)*4+x+1)>>1;
return n;
}
std::vector<int> get_counts(const std::vector<std::string>&M){
std::vector<int>counts(4);
for(int y=0;y<8;++y)for(int x=0;x<8;++x)counts[y/4*2+x/4]+=M[y][x]=='M';
return counts;
}
int balance(const std::vector<int>&counts){
int b=0;
for(int c:counts)b+=abs(c-8);
return b;
}
void rot(std::vector<std::string>&M,int x,int y){
std::swap(M[y][x],M[y][x+1]);
std::swap(M[y+1][x],M[y][x]);
std::swap(M[y+1][x+1],M[y+1][x]);
}
std::vector<int> solve(std::vector<std::string>M){
std::vector<int>solution;
for(;;){
auto cs=get_counts(M);
if(cs[0]==8&&cs[1]==8&&cs[2]==8)break;
for(int y=0;y<7;++y){
for(int x=0;x<7;++x){
rot(M,x,y);
auto cs2=get_counts(M);
if(balance(cs2)<balance(cs)){
solution.push_back(y*8+x);
goto next;
}
else{
rot(M,x,y);
rot(M,x,y);
rot(M,x,y);
}
}
}
{
int x=rand7();
int y=rand7();
rot(M,x,y);
solution.push_back(y*8+x);
}
next:;
}
for(int Y=0;Y<2;++Y)for(int X=0;X<2;++X){
auto block=0u;
for(int y=0;y<4;++y)for(int x=0;x<4;++x)
if(M[Y*4+y][X*4+x]=='M')block|=1<<y*4+x;
while(depth_4x4[block]){
auto yx=yx_4x4[block];
auto y=yx/4+Y*4;
auto x=yx%4+X*4;
solution.push_back(y*8+x);
block=rot_4x4(block,yx%4,yx/4);
}
}
return solution;
}
int main(){
for(int i=0;i<P16;++i)depth_4x4[i]=999999;
unsigned solved=0x5A5A;
depth_4x4[solved]=0;
for(unsigned depth=1;;++depth){
std::unordered_set<unsigned>prev;
for(int i=0;i<P16;++i)if(depth_4x4[i]==depth-1)prev.insert(i);
if(prev.empty())break;
for(auto p:prev)for(int y=0;y<3;++y)for(int x=0;x<3;++x){
auto n=rot_4x4(p,x,y);
n=rot_4x4(n,x,y);
n=rot_4x4(n,x,y);
if(depth_4x4[n]>depth){
depth_4x4[n]=depth;
yx_4x4[n]=y*4+x;
}
}
}
std::vector<std::string>M(8);
for(auto&s:M)std::cin>>s;
auto solution=solve(M);
for(auto&s:M)for(auto&c:s)c="MV"[c=='M'];
auto solution2=solve(M);
if(solution2.size()<solution.size())solution=std::move(solution2);
std::cout<<solution.size()<<'\n';
for(int yx:solution)std::cout<<yx%8+1<<' '<<yx/8+1<<'\n';
}

Test details

Test 1

Group: 1

Verdict: ACCEPTED

input
VMMVVMVV
MMVVMVVV
MMVVMMMM
MVVVMVVM
MVVVVMVM
...

correct output
100000

user output
26
1 4
2 3
3 1
3 3
...

Test 2

Group: 1

Verdict: ACCEPTED

input
MVMVVMMV
VVMMVVVV
VMMVMMVM
MVVVVMVM
MVMVMMVM
...

correct output
100000

user output
23
1 4
6 4
3 2
2 2
...

Test 3

Group: 1

Verdict: ACCEPTED

input
VMMMVMVV
MMMVMVMV
VMMVMVVM
VVVMVMMV
MVMVMVMV
...

correct output
100000

user output
25
4 4
1 3
1 3
2 3
...

Test 4

Group: 1

Verdict: ACCEPTED

input
VVVMVMVV
VMMVMVMM
MVVMMVMV
VMVMMVMM
MMVVMMVM
...

correct output
100000

user output
37
4 2
4 6
6 1
2 6
...

Test 5

Group: 1

Verdict: ACCEPTED

input
MVMVVMMM
VVMMVVMV
MVVMVVMM
VMVMVMMV
MMVMVVVM
...

correct output
100000

user output
99
6 1
2 6
6 5
1 7
...

Test 6

Group: 1

Verdict: ACCEPTED

input
VMMVMVVM
VVMMVVMM
MMMVMVVM
VMMVMMVM
MVMVMMMV
...

correct output
100000

user output
23
2 4
4 4
1 2
1 1
...

Test 7

Group: 1

Verdict: ACCEPTED

input
MVVVVMMM
MMMMMMMM
VVVVVMMV
MMVVMVVM
VMVVVVMV
...

correct output
100000

user output
62
4 1
6 1
2 6
6 5
...

Test 8

Group: 1

Verdict: ACCEPTED

input
VMMVMVMM
MMMVVMMM
MVVVVVVV
VVVVMMMV
MVVVMVVM
...

correct output
100000

user output
46
4 3
1 4
6 1
2 6
...

Test 9

Group: 1

Verdict: ACCEPTED

input
VVVVVMMM
MMVVVVVV
MVVVMMMM
VVMVVVVM
VMMVMVMM
...

correct output
100000

user output
52
3 4
6 1
2 6
6 5
...

Test 10

Group: 1

Verdict: ACCEPTED

input
VMMVMMMM
VVMVVVVV
VMMVMVMV
VMMVMVMM
VVVMMMMM
...

correct output
100000

user output
24
4 2
1 2
1 3
3 1
...

Test 11

Group: 2

Verdict: ACCEPTED

input
VMVMVVMM
MMVMVVMM
VMVVVMMV
VVVMVMVM
VVMMVVMM
...

correct output
25000

user output
38
4 5
4 5
7 2
3 1
...

Test 12

Group: 2

Verdict: ACCEPTED

input
MVMVVMVV
VMMVVMVM
VMVVVMMM
VMMMMVVM
MMVVVMMM
...

correct output
25000

user output
39
4 6
6 1
2 6
6 5
...

Test 13

Group: 2

Verdict: ACCEPTED

input
MVVMMVVV
MMVVMVMM
VVVMVMVV
VMVMMMMM
MVVMMVMV
...

correct output
25000

user output
38
6 1
2 6
6 5
1 7
...

Test 14

Group: 2

Verdict: ACCEPTED

input
VVMMMVMV
VMVVVMVV
VVMVVVMM
MVVMVMVM
MMVVMMMM
...

correct output
25000

user output
46
1 4
6 1
2 6
6 5
...

Test 15

Group: 2

Verdict: ACCEPTED

input
MVVVMVVV
MMMMVMMM
MVMMMVVM
MMVVVMVM
VMVVVMMV
...

correct output
25000

user output
64
1 4
1 3
3 7
5 4
...

Test 16

Group: 2

Verdict: ACCEPTED

input
VMMVMVVM
VMMVVVVV
MVMVMMVM
VMMVVVMV
VVMVMMVM
...

correct output
25000

user output
23
5 4
5 4
3 3
2 2
...

Test 17

Group: 2

Verdict: ACCEPTED

input
MVVMMVVM
MVVVMMMV
MVVMMVVM
VMMVMVMV
VMMVMMMM
...

correct output
25000

user output
23
4 2
1 1
3 1
2 1
...

Test 18

Group: 2

Verdict: ACCEPTED

input
MVMMVVMM
VVMMMMVV
VMVVVVVM
MVMMMVMV
VMVVVMVM
...

correct output
25000

user output
18
4 2
3 1
3 3
3 2
...

Test 19

Group: 2

Verdict: ACCEPTED

input
MVVVVVVV
VMMVMVVM
VMVMMMMV
MVMVMMMM
MMVVVMMM
...

correct output
25000

user output
28
4 1
4 5
2 1
1 1
...

Test 20

Group: 2

Verdict: ACCEPTED

input
MVVVMMMM
MMVMMVMV
MVVVVVMM
VVMMMVVM
VVVMVMVV
...

correct output
25000

user output
24
4 1
7 4
3 3
1 2
...

Test 21

Group: 3

Verdict: ACCEPTED

input
VMVVMVMM
MMMMVMMV
VVVMVVVV
MVMVMVVM
VMMVMMMM
...

correct output
5000

user output
18
5 4
2 1
3 2
3 1
...

Test 22

Group: 3

Verdict: ACCEPTED

input
VVVVVVMM
MMMVMMVV
VVVVVVMV
MMMVMVVV
MVVMMMMV
...

correct output
5000

user output
50
5 4
7 4
4 2
7 1
...

Test 23

Group: 3

Verdict: ACCEPTED

input
MMVMVMVV
MMVVMVVM
VMMVVMVM
MMMMMMVV
MVVVVMVM
...

correct output
5000

user output
80
4 4
1 5
3 5
7 3
...

Test 24

Group: 3

Verdict: ACCEPTED

input
MVMVVMVM
VVMVVMVM
MMMMVMVV
MVVMMVVV
MMMMMVVV
...

correct output
5000

user output
85
4 5
6 1
2 6
6 5
...

Test 25

Group: 3

Verdict: ACCEPTED

input
MVVVMVVM
MMMMVVMV
VMMVMMVV
VVMVMVMV
MVMMMVMM
...

correct output
5000

user output
36
6 1
2 6
6 5
1 7
...

Test 26

Group: 3

Verdict: ACCEPTED

input
VMVMVVVM
MMMVVVMM
MMVVVVVM
VVVVMMVV
VMMVVMMV
...

correct output
5000

user output
50
6 4
7 2
3 1
4 4
...

Test 27

Group: 3

Verdict: ACCEPTED

input
MMVMMVVM
MVVVMVMV
MVVVMVVM
VMVMMMVV
VMMVVVVV
...

correct output
5000

user output
26
2 4
4 7
3 3
1 1
...

Test 28

Group: 3

Verdict: ACCEPTED

input
MVMMVMMV
VMVMMMVV
MMMMVVMV
VVVVMMMM
MMMVMMVV
...

correct output
5000

user output
43
7 4
6 1
2 6
6 5
...

Test 29

Group: 3

Verdict: ACCEPTED

input
VVVVMVMV
MMMVVMVM
MVVVMVMV
VVVMVVMM
VMMMMMVV
...

correct output
5000

user output
36
2 4
2 4
6 1
2 6
...

Test 30

Group: 3

Verdict: ACCEPTED

input
MVVVMVVV
MMVVMMMM
MVVVVVVV
MVMVMMMV
VMMMVMMM
...

correct output
5000

user output
56
6 1
2 6
6 5
1 7
...

Test 31

Group: 4

Verdict: ACCEPTED

input
MVMMVMMV
VVVMMVVV
VMMVVMMV
VVMMMVVM
VVVMMMVV
...

correct output
250

user output
36
5 4
4 6
7 7
6 6
...

Test 32

Group: 4

Verdict: ACCEPTED

input
VVMMVVVM
VMVVMMVV
VMMMMMMV
VVMVMVVV
VMMVMVMM
...

correct output
250

user output
31
5 4
6 1
2 6
6 5
...

Test 33

Group: 4

Verdict: ACCEPTED

input
MMVVMVMV
VVVMVMMM
VVVVMVMM
MVVMVVMV
VMMVMVVM
...

correct output
250

user output
71
4 5
7 6
2 3
4 6
...

Test 34

Group: 4

Verdict: ACCEPTED

input
VMVMVVMV
MVVMMMMM
MMVVMMMM
VMVMVVVM
VMMMVVVM
...

correct output
250

user output
84
7 4
4 5
6 1
2 6
...

Test 35

Group: 4

Verdict: ACCEPTED

input
VMVMVMMM
VMMVVVMM
MMVMVMMM
MVMMVVVV
VMMVMMMV
...

correct output
250

user output
143
4 4
6 1
2 6
6 5
...

Test 36

Group: 4

Verdict: ACCEPTED

input
MVMVMVMM
MVMVMMMV
MMVVVVMM
MVMVVVVV
VMMMVVMM
...

correct output
250

user output
23
1 1
3 1
3 1
1 1
...

Test 37

Group: 4

Verdict: ACCEPTED

input
VMMMMVMM
VVMMMVMV
VMVVVVVV
MVMMMVVM
VMVMMVVM
...

correct output
250

user output
24
4 2
2 2
3 3
1 2
...

Test 38

Group: 4

Verdict: ACCEPTED

input
VMMVMVMV
VVMVMVMM
MMMVMVMM
MVVVVMMM
MMVVVMVV
...

correct output
250

user output
29
4 1
5 4
7 4
3 2
...

Test 39

Group: 4

Verdict: ACCEPTED

input
MMMMMVMV
MVVMMMMV
VMVVVVMM
VMVVVMMV
MVMMMVMM
...

correct output
250

user output
103
1 5
3 5
7 3
7 6
...

Test 40

Group: 4

Verdict: ACCEPTED

input
VMMMMMMV
VMMVVVVV
MVMMVMMV
MVVVVMMV
MVVVVMMM
...

correct output
250

user output
23
4 1
4 5
1 2
1 1
...