Task: | Shakki |
Sender: | |
Submission time: | 2015-12-04 21:52:02 +0200 |
Language: | C++ |
Status: | READY |
Result: | 100 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 28 |
#2 | ACCEPTED | 21 |
#3 | ACCEPTED | 24 |
#4 | ACCEPTED | 27 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.06 s | 1 | details |
#2 | ACCEPTED | 0.07 s | 1 | details |
#3 | ACCEPTED | 0.06 s | 1 | details |
#4 | ACCEPTED | 0.05 s | 1 | details |
#5 | ACCEPTED | 0.06 s | 1 | details |
#6 | ACCEPTED | 0.05 s | 1 | details |
#7 | ACCEPTED | 0.05 s | 1 | details |
#8 | ACCEPTED | 0.06 s | 1 | details |
#9 | ACCEPTED | 0.06 s | 1 | details |
#10 | ACCEPTED | 0.06 s | 1 | details |
#11 | ACCEPTED | 0.06 s | 2 | details |
#12 | ACCEPTED | 0.06 s | 2 | details |
#13 | ACCEPTED | 0.06 s | 2 | details |
#14 | ACCEPTED | 0.06 s | 2 | details |
#15 | ACCEPTED | 0.06 s | 2 | details |
#16 | ACCEPTED | 0.06 s | 2 | details |
#17 | ACCEPTED | 0.05 s | 2 | details |
#18 | ACCEPTED | 0.05 s | 2 | details |
#19 | ACCEPTED | 0.05 s | 2 | details |
#20 | ACCEPTED | 0.06 s | 2 | details |
#21 | ACCEPTED | 0.06 s | 3 | details |
#22 | ACCEPTED | 0.05 s | 3 | details |
#23 | ACCEPTED | 0.06 s | 3 | details |
#24 | ACCEPTED | 0.05 s | 3 | details |
#25 | ACCEPTED | 0.05 s | 3 | details |
#26 | ACCEPTED | 0.06 s | 3 | details |
#27 | ACCEPTED | 0.05 s | 3 | details |
#28 | ACCEPTED | 0.05 s | 3 | details |
#29 | ACCEPTED | 0.06 s | 3 | details |
#30 | ACCEPTED | 0.06 s | 3 | details |
#31 | ACCEPTED | 0.06 s | 4 | details |
#32 | ACCEPTED | 0.05 s | 4 | details |
#33 | ACCEPTED | 0.05 s | 4 | details |
#34 | ACCEPTED | 0.06 s | 4 | details |
#35 | ACCEPTED | 0.05 s | 4 | details |
#36 | ACCEPTED | 0.06 s | 4 | details |
#37 | ACCEPTED | 0.05 s | 4 | details |
#38 | ACCEPTED | 0.05 s | 4 | details |
#39 | ACCEPTED | 0.05 s | 4 | details |
#40 | ACCEPTED | 0.05 s | 4 | details |
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 ... |