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

Code

#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef long double ld;
string s[10];
string ss[10];
vector<pair<int, int> > v;
void pr(){
for (int i=0;i<8;i++){
cout<<s[i]<<endl;
}
cout<<endl;
}
void turn(int y, int x){
assert(y>=0);
assert(x>=0);
assert(y<7);
assert(x<7);
v.push_back({x+1, y+1});
char t=s[y][x];
s[y][x]=s[y+1][x];
s[y+1][x]=s[y+1][x+1];
s[y+1][x+1]=s[y][x+1];
s[y][x+1]=t;
}
int checkh(int y){
int c=0;
for (int i=0;i<=y;i++){
for (int j=0;j<8;j++){
if (s[i][j]=='M') c++;
else c--;
}
}
return c;
}
int checkv(int x){
int c=0;
for (int i=0;i<=x;i++){
for (int j=0;j<8;j++){
if (s[j][i]=='M') c++;
else c--;
}
}
return c;
}
int asd(){
for (int i=0;i<7;i++){
for (int ii=0;ii<7;ii++){
if (s[i][ii]=='V'&&s[i][ii+1]=='V'&&s[i+1][ii]=='M'&&s[i+1][ii+1]=='M'){
if (checkh(i)<=-4){
turn(i, ii);
turn(i, ii);
return 1;
}
}
if (s[i][ii]=='M'&&s[i][ii+1]=='M'&&s[i+1][ii]=='V'&&s[i+1][ii+1]=='V'){
if (checkh(i)>=4){
turn(i, ii);
turn(i, ii);
return 1;
}
}
}
}
for (int i=0;i<7;i++){
for (int ii=0;ii<7;ii++){
if (s[i][ii]=='V'&&s[i][ii+1]=='M'&&s[i+1][ii]=='V'&&s[i+1][ii+1]=='M'){
if (checkv(ii)<=-4){
turn(i, ii);
turn(i, ii);
return 1;
}
}
if (s[i][ii]=='M'&&s[i][ii+1]=='V'&&s[i+1][ii]=='M'&&s[i+1][ii+1]=='V'){
if (checkv(ii)>=4){
turn(i, ii);
turn(i, ii);
return 1;
}
}
}
}
return 0;
for (int i=0;i<7;i++){
for (int ii=0;ii<7;ii++){
// VV
// VM
int ts=-1;
if (s[i][ii]=='V'&&s[i][ii+1]=='V'&&s[i+1][ii]=='V'&&s[i+1][ii+1]=='M'){
ts=0;
}
// VV
// MV
if (s[i][ii]=='V'&&s[i][ii+1]=='V'&&s[i+1][ii]=='M'&&s[i+1][ii+1]=='V'){
ts=1;
}
// MV
// VV
if (s[i][ii]=='M'&&s[i][ii+1]=='V'&&s[i+1][ii]=='V'&&s[i+1][ii+1]=='V'){
ts=2;
}
// VM
// VV
if (s[i][ii]=='V'&&s[i][ii+1]=='M'&&s[i+1][ii]=='V'&&s[i+1][ii+1]=='V'){
ts=3;
}
if (ts>-1){
int ns=-1;
if (checkv(ii)<=-2) ns=1;
if (checkh(i)<=-2) ns=2;
if (checkv(ii)>=2) ns=3;
if (checkh(i)>=2) ns=0;
if (ns>-1){
int t=(ns-ts+4)%4;
if (t>0){
for (int j=0;j<t;j++){
turn(i, ii);
}
return 1;
}
}
}
// VV
// VM
ts=-1;
if (s[i][ii]!='V'&&s[i][ii+1]!='V'&&s[i+1][ii]!='V'&&s[i+1][ii+1]!='M'){
ts=0;
}
// VV
// MV
if (s[i][ii]!='V'&&s[i][ii+1]!='V'&&s[i+1][ii]!='M'&&s[i+1][ii+1]!='V'){
ts=1;
}
// MV
// VV
if (s[i][ii]!='M'&&s[i][ii+1]!='V'&&s[i+1][ii]!='V'&&s[i+1][ii+1]!='V'){
ts=2;
}
// VM
// VV
if (s[i][ii]!='V'&&s[i][ii+1]!='M'&&s[i+1][ii]!='V'&&s[i+1][ii+1]!='V'){
ts=3;
}
if (ts>-1){
int ns=-1;
if (checkv(ii)>=2) ns=1;
if (checkh(i)>=2) ns=2;
if (checkv(ii)<=-2) ns=3;
if (checkh(i)<=-2) ns=0;
if (ns>-1){
int t=(ns-ts+4)%4;
if (t>0){
for (int j=0;j<t;j++){
turn(i, ii);
}
return 1;
}
}
}
}
}
return 0;
}
void up(char c, int y){
for (int i=y;i<7;i++){
for (int ii=0;ii<7;ii++){
if (s[i][ii]==c&&s[i][ii+1]==c) continue;
if (s[i][ii]!=c&&s[i][ii+1]!=c){
if (s[i+1][ii]==c){
turn(i, ii);
return;
}
if (s[i+1][ii+1]==c){
turn(i, ii);
turn(i, ii);
return;
}
}
if (s[i][ii]==c){
if (s[i+1][ii]==c){
turn(i, ii);
return;
}
}
if (s[i][ii+1]==c){
if (s[i+1][ii]==c&&s[i+1][ii+1]==c){
turn(i, ii);
turn(i, ii);
return;
}
if (s[i+1][ii+1]==c){
turn(i, ii);
turn(i, ii);
turn(i, ii);
return;
}
}
}
}
}
void left(char c, int y, int x){
for (int ii=x;ii<7;ii++){
if (s[y][ii]==c&&s[y+1][ii]==c) continue;
if (s[y][ii]!=c&&s[y+1][ii]!=c){
if (s[y+1][ii+1]==c){
turn(y, ii);
return;
}
if (s[y+1][ii]==c){
turn(y, ii);
turn(y, ii);
return;
}
}
if (s[y+1][ii]==c){
if (s[y+1][ii+1]==c){
turn(y, ii);
return;
}
}
if (s[y][ii]==c){
if (s[y][ii+1]==c&&s[y+1][ii+1]==c){
turn(y, ii);
turn(y, ii);
return;
}
if (s[y][ii+1]==c){
turn(y, ii);
turn(y, ii);
turn(y, ii);
return;
}
}
}
}
void gen(int t){
for (int i=0;i<t;i++){
int a=rand()%7;
int b=rand()%7;
turn(a, b);
}
}
void trs(){
v.clear();
for (int i=0;i<8;i++){
s[i]=ss[i];
}
gen(100);
for (int i=0;i<7;i++){
while (1){
int c=0;
for (int ii=0;ii<8;ii++){
if (s[i][ii]=='V') c++;
else c--;
}
if (c==0) break;
if (c>0){
up('M', i);
}
else{
up('V', i);
}
}
}
for (int i=0;i<8;i+=2){
for (int ii=0;ii<7;ii++){
while (1){
if (s[i][ii]=='V'&&s[i+1][ii]=='V'){
left('M', i, ii);
}
else if(s[i][ii]=='M'&&s[i+1][ii]=='M'){
left('V', i, ii);
}
else{
break;
}
//cout<<i<<" "<<ii<<endl;
//pr();
}
}
}
//pr();
for (int i=0;i<8;i+=2){
for (int ii=0;ii<6;ii++){
while (1){
if (s[i][ii]==s[i][ii+1]&&s[i][ii+1]==s[i][ii+2]){
turn(i, ii+1);
turn(i, ii+1);
}
else{
break;
}
//cout<<i<<" "<<ii<<endl;
//pr();
}
}
}
//pr();
for (int i=0;i<8;i+=2){
for (int ii=0;ii<6;ii++){
while (1){
if (s[i][ii]==s[i][ii+1]){
for (int j=ii+1;j<7;j+=2){
if (s[i][j]==s[i][j+1]){
turn(i, j);
turn(i, j);
}
else{
turn(i, j);
}
}
}
else{
break;
}
//cout<<i<<" "<<ii<<endl;
//pr();
}
}
}
for (int i=0;i<7;i++){
for (int ii=0;ii<7;ii++){
if (s[i][ii]==s[i][ii+1]) return;
if (s[i][ii]==s[i+1][ii]) return;
}
}
for (int i=0;i<8;i+=2){
for (int ii=0;ii<8;ii+=2){
if (s[i][ii]!='M') turn(i, ii);
}
}
cout<<v.size()<<endl;
for (auto vv:v){
cout<<vv.F<<" "<<vv.S<<endl;
}
exit(0);
}
int main(){
srand(time(0));
ios_base::sync_with_stdio(0);
cin.tie(0);
for (int i=0;i<8;i++){
cin>>ss[i];
s[i]=ss[i];
}
//gen(1000);
while (1){
trs();
//cout<<"try"<<endl;
}
}

Test details

Test 1

Group: 1

Verdict: ACCEPTED

input
VMMVVMVV
MMVVMVVV
MMVVMMMM
MVVVMVVM
MVVVVMVM
...

correct output
100000

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

Test 2

Group: 1

Verdict: ACCEPTED

input
MVMVVMMV
VVMMVVVV
VMMVMMVM
MVVVVMVM
MVMVMMVM
...

correct output
100000

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

Test 3

Group: 1

Verdict: ACCEPTED

input
VMMMVMVV
MMMVMVMV
VMMVMVVM
VVVMVMMV
MVMVMVMV
...

correct output
100000

user output
185
7 6
5 7
6 5
4 2
...

Test 4

Group: 1

Verdict: ACCEPTED

input
VVVMVMVV
VMMVMVMM
MVVMMVMV
VMVMMVMM
MMVVMMVM
...

correct output
100000

user output
172
3 4
5 5
2 5
2 4
...

Test 5

Group: 1

Verdict: ACCEPTED

input
MVMVVMMM
VVMMVVMV
MVVMVVMM
VMVMVMMV
MMVMVVVM
...

correct output
100000

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

Test 6

Group: 1

Verdict: ACCEPTED

input
VMMVMVVM
VVMMVVMM
MMMVMVVM
VMMVMMVM
MVMVMMMV
...

correct output
100000

user output
194
3 6
2 5
6 2
7 3
...

Test 7

Group: 1

Verdict: ACCEPTED

input
MVVVVMMM
MMMMMMMM
VVVVVMMV
MMVVMVVM
VMVVVVMV
...

correct output
100000

user output
186
5 5
1 4
3 3
1 4
...

Test 8

Group: 1

Verdict: ACCEPTED

input
VMMVMVMM
MMMVVMMM
MVVVVVVV
VVVVMMMV
MVVVMVVM
...

correct output
100000

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

Test 9

Group: 1

Verdict: ACCEPTED

input
VVVVVMMM
MMVVVVVV
MVVVMMMM
VVMVVVVM
VMMVMVMM
...

correct output
100000

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

Test 10

Group: 1

Verdict: ACCEPTED

input
VMMVMMMM
VVMVVVVV
VMMVMVMV
VMMVMVMM
VVVMMMMM
...

correct output
100000

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

Test 11

Group: 2

Verdict: ACCEPTED

input
VMVMVVMM
MMVMVVMM
VMVVVMMV
VVVMVMVM
VVMMVVMM
...

correct output
25000

user output
164
1 1
7 7
2 3
3 6
...

Test 12

Group: 2

Verdict: ACCEPTED

input
MVMVVMVV
VMMVVMVM
VMVVVMMM
VMMMMVVM
MMVVVMMM
...

correct output
25000

user output
165
1 6
7 1
4 3
1 7
...

Test 13

Group: 2

Verdict: ACCEPTED

input
MVVMMVVV
MMVVMVMM
VVVMVMVV
VMVMMMMM
MVVMMVMV
...

correct output
25000

user output
166
4 6
3 7
7 1
4 3
...

Test 14

Group: 2

Verdict: ACCEPTED

input
VVMMMVMV
VMVVVMVV
VVMVVVMM
MVVMVMVM
MMVVMMMM
...

correct output
25000

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

Test 15

Group: 2

Verdict: ACCEPTED

input
MVVVMVVV
MMMMVMMM
MVMMMVVM
MMVVVMVM
VMVVVMMV
...

correct output
25000

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

Test 16

Group: 2

Verdict: ACCEPTED

input
VMMVMVVM
VMMVVVVV
MVMVMMVM
VMMVVVMV
VVMVMMVM
...

correct output
25000

user output
180
1 4
5 1
6 5
7 6
...

Test 17

Group: 2

Verdict: ACCEPTED

input
MVVMMVVM
MVVVMMMV
MVVMMVVM
VMMVMVMV
VMMVMMMM
...

correct output
25000

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

Test 18

Group: 2

Verdict: ACCEPTED

input
MVMMVVMM
VVMMMMVV
VMVVVVVM
MVMMMVMV
VMVVVMVM
...

correct output
25000

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

Test 19

Group: 2

Verdict: ACCEPTED

input
MVVVVVVV
VMMVMVVM
VMVMMMMV
MVMVMMMM
MMVVVMMM
...

correct output
25000

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

Test 20

Group: 2

Verdict: ACCEPTED

input
MVVVMMMM
MMVMMVMV
MVVVVVMM
VVMMMVVM
VVVMVMVV
...

correct output
25000

user output
152
2 6
7 5
3 1
4 6
...

Test 21

Group: 3

Verdict: ACCEPTED

input
VMVVMVMM
MMMMVMMV
VVVMVVVV
MVMVMVVM
VMMVMMMM
...

correct output
5000

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

Test 22

Group: 3

Verdict: ACCEPTED

input
VVVVVVMM
MMMVMMVV
VVVVVVMV
MMMVMVVV
MVVMMMMV
...

correct output
5000

user output
188
3 3
5 2
2 1
6 2
...

Test 23

Group: 3

Verdict: ACCEPTED

input
MMVMVMVV
MMVVMVVM
VMMVVMVM
MMMMMMVV
MVVVVMVM
...

correct output
5000

user output
196
4 6
6 3
5 2
3 2
...

Test 24

Group: 3

Verdict: ACCEPTED

input
MVMVVMVM
VVMVVMVM
MMMMVMVV
MVVMMVVV
MMMMMVVV
...

correct output
5000

user output
188
6 6
7 7
1 7
7 7
...

Test 25

Group: 3

Verdict: ACCEPTED

input
MVVVMVVM
MMMMVVMV
VMMVMMVV
VVMVMVMV
MVMMMVMM
...

correct output
5000

user output
192
1 3
1 7
2 1
5 1
...

Test 26

Group: 3

Verdict: ACCEPTED

input
VMVMVVVM
MMMVVVMM
MMVVVVVM
VVVVMMVV
VMMVVMMV
...

correct output
5000

user output
197
1 6
7 1
4 3
1 7
...

Test 27

Group: 3

Verdict: ACCEPTED

input
MMVMMVVM
MVVVMVMV
MVVVMVVM
VMVMMMVV
VMMVVVVV
...

correct output
5000

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

Test 28

Group: 3

Verdict: ACCEPTED

input
MVMMVMMV
VMVMMMVV
MMMMVVMV
VVVVMMMM
MMMVMMVV
...

correct output
5000

user output
192
5 6
5 4
7 6
5 1
...

Test 29

Group: 3

Verdict: ACCEPTED

input
VVVVMVMV
MMMVVMVM
MVVVMVMV
VVVMVVMM
VMMMMMVV
...

correct output
5000

user output
202
2 6
7 2
7 7
7 7
...

Test 30

Group: 3

Verdict: ACCEPTED

input
MVVVMVVV
MMVVMMMM
MVVVVVVV
MVMVMMMV
VMMMVMMM
...

correct output
5000

user output
174
3 2
4 1
5 6
4 7
...

Test 31

Group: 4

Verdict: ACCEPTED

input
MVMMVMMV
VVVMMVVV
VMMVVMMV
VVMMMVVM
VVVMMMVV
...

correct output
250

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

Test 32

Group: 4

Verdict: ACCEPTED

input
VVMMVVVM
VMVVMMVV
VMMMMMMV
VVMVMVVV
VMMVMVMM
...

correct output
250

user output
173
2 5
2 6
3 3
7 5
...

Test 33

Group: 4

Verdict: ACCEPTED

input
MMVVMVMV
VVVMVMMM
VVVVMVMM
MVVMVVMV
VMMVMVVM
...

correct output
250

user output
184
5 3
3 5
7 7
3 7
...

Test 34

Group: 4

Verdict: ACCEPTED

input
VMVMVVMV
MVVMMMMM
MMVVMMMM
VMVMVVVM
VMMMVVVM
...

correct output
250

user output
206
5 3
6 6
2 5
7 1
...

Test 35

Group: 4

Verdict: ACCEPTED

input
VMVMVMMM
VMMVVVMM
MMVMVMMM
MVMMVVVV
VMMVMMMV
...

correct output
250

user output
186
7 3
3 5
6 7
3 6
...

Test 36

Group: 4

Verdict: ACCEPTED

input
MVMVMVMM
MVMVMMMV
MMVVVVMM
MVMVVVVV
VMMMVVMM
...

correct output
250

user output
185
6 2
4 6
4 4
5 6
...

Test 37

Group: 4

Verdict: ACCEPTED

input
VMMMMVMM
VVMMMVMV
VMVVVVVV
MVMMMVVM
VMVMMVVM
...

correct output
250

user output
186
5 5
3 2
6 2
3 2
...

Test 38

Group: 4

Verdict: ACCEPTED

input
VMMVMVMV
VVMVMVMM
MMMVMVMM
MVVVVMMM
MMVVVMVV
...

correct output
250

user output
199
1 6
1 3
5 6
4 6
...

Test 39

Group: 4

Verdict: ACCEPTED

input
MMMMMVMV
MVVMMMMV
VMVVVVMM
VMVVVMMV
MVMMMVMM
...

correct output
250

user output
192
5 2
6 7
1 3
4 7
...

Test 40

Group: 4

Verdict: ACCEPTED

input
VMMMMMMV
VMMVVVVV
MVMMVMMV
MVVVVMMV
MVVVVMMM
...

correct output
250

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