oj.uz

Submission #114341

# Submission time Handle Problem Language Result Execution time Memory
114341 2019-06-01T01:24:39 Z sebinkim Lock Puzzle (innopolis2018_final_A) C++14
9 / 100
 2 ms 384 KB 
#include <bits/stdc++.h>

using namespace std;

char A[2020], B[2020];
int D[2020], E[2020];
vector <int> V;
int n, m;

void shift(int p)
{
	reverse(A, A + n);
	reverse(A + p, A + n);
	V.push_back(p);
}

int main()
{
	int i, j;
	
	scanf("%d%d", &n, &m);
	scanf("%s%s", A, B);
	
	if(n & 1){
		D[0] = 0;
		for(i=1; i<n; i+=2){
			reverse(D, D + i);
			for(j=i; j>=1; j--) D[j] = D[j - 1];
			D[i + 1] = i; D[0] = i + 1;
		}
		
		for(i=0; i<n; i++){
			E[D[i]] = i;
		}
		
		for(i=0; i<n; i++){
			if(A[i] == B[E[0]]) break; 
		}
		
		shift(n - i);
		
		for(i=1; i<n; i+=2){
			for(j=0; j<n-i; j++){
				if(A[j] == B[E[i]]) break;
			}
			
			if(j == n - i){
				printf("-1\n");
				return 0;
			}
			
			shift(n - j - 1); shift(n); shift(i);
			
			for(j=i+1; j<n; j++){
				if(A[j] == B[E[i + 1]]) break;
			}
			
			if(j == n){
				printf("-1\n");
				return 0;
			}
			
			shift(n - j); shift(j - i - 1);
		}
	}
	else{
		for(i=0; i<n; i+=2){
			reverse(D, D + i);
			for(j=i; j>=1; j--) D[j] = D[j - 1];
			D[i + 1] = i; D[0] = i + 1;
		}
		
		for(i=0; i<n; i++){
			E[D[i]] = i;
		}
		
		for(i=0; i<n; i+=2){
			for(j=0; j<n-i; j++){
				if(A[j] == B[E[i]]) break;
			}
			
			if(j == n - i){
				printf("-1\n");
				return 0;
			}
			
			shift(n - j - 1); shift(n); shift(i);
			
			for(j=i+1; j<n; j++){
				if(A[j] == B[E[i + 1]]) break;
			}
			
			if(j == n){
				printf("-1\n");
				return 0;
			}
			
			shift(n - j); shift(j - i - 1);
		}
	}
	
	printf("%d\n", V.size());
	
	for(int &t: V) printf("%d ", t);
	
	printf("\n");
	
	return 0;
}

Compilation message

A.cpp: In function 'int main()':
A.cpp:102:25: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
  printf("%d\n", V.size());
                 ~~~~~~~~^
A.cpp:21:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~
A.cpp:22:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s%s", A, B);
  ~~~~~^~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB [n = 1, m = 10000], OK, 1 operations
2 Correct 2 ms 384 KB [n = 2, m = 10000], OK, 5 operations
3 Correct 2 ms 256 KB [n = 8, m = 10000], OK, 20 operations
4 Correct 2 ms 384 KB [n = 8, m = 10000], OK, 20 operations
5 Correct 2 ms 384 KB [n = 8, m = 10000], OK, 20 operations
6 Correct 2 ms 384 KB [n = 8, m = 10000], OK: No solution
7 Correct 2 ms 256 KB [n = 8, m = 10000], OK, 20 operations
8 Correct 2 ms 256 KB [n = 8, m = 10000], OK, 20 operations

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB [n = 1, m = 10000], OK, 1 operations
2 Correct 2 ms 384 KB [n = 2, m = 10000], OK, 5 operations
3 Correct 2 ms 256 KB [n = 8, m = 10000], OK, 20 operations
4 Correct 2 ms 384 KB [n = 8, m = 10000], OK, 20 operations
5 Correct 2 ms 384 KB [n = 8, m = 10000], OK, 20 operations
6 Correct 2 ms 384 KB [n = 8, m = 10000], OK: No solution
7 Correct 2 ms 256 KB [n = 8, m = 10000], OK, 20 operations
8 Correct 2 ms 256 KB [n = 8, m = 10000], OK, 20 operations
9 Incorrect 2 ms 384 KB [n = 49, m = 10000] No solution found, but it exists
10 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB [n = 1, m = 10000], OK, 1 operations
2 Correct 2 ms 384 KB [n = 2, m = 10000], OK, 5 operations
3 Correct 2 ms 256 KB [n = 8, m = 10000], OK, 20 operations
4 Correct 2 ms 384 KB [n = 8, m = 10000], OK, 20 operations
5 Correct 2 ms 384 KB [n = 8, m = 10000], OK, 20 operations
6 Correct 2 ms 384 KB [n = 8, m = 10000], OK: No solution
7 Correct 2 ms 256 KB [n = 8, m = 10000], OK, 20 operations
8 Correct 2 ms 256 KB [n = 8, m = 10000], OK, 20 operations
9 Incorrect 2 ms 384 KB [n = 49, m = 10000] No solution found, but it exists
10 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB [n = 1, m = 10000], OK, 1 operations
2 Correct 2 ms 384 KB [n = 2, m = 10000], OK, 5 operations
3 Correct 2 ms 256 KB [n = 8, m = 10000], OK, 20 operations
4 Correct 2 ms 384 KB [n = 8, m = 10000], OK, 20 operations
5 Correct 2 ms 384 KB [n = 8, m = 10000], OK, 20 operations
6 Correct 2 ms 384 KB [n = 8, m = 10000], OK: No solution
7 Correct 2 ms 256 KB [n = 8, m = 10000], OK, 20 operations
8 Correct 2 ms 256 KB [n = 8, m = 10000], OK, 20 operations
9 Incorrect 2 ms 384 KB [n = 49, m = 10000] No solution found, but it exists
10 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB [n = 1, m = 10000], OK, 1 operations
2 Correct 2 ms 384 KB [n = 2, m = 10000], OK, 5 operations
3 Correct 2 ms 256 KB [n = 8, m = 10000], OK, 20 operations
4 Correct 2 ms 384 KB [n = 8, m = 10000], OK, 20 operations
5 Correct 2 ms 384 KB [n = 8, m = 10000], OK, 20 operations
6 Correct 2 ms 384 KB [n = 8, m = 10000], OK: No solution
7 Correct 2 ms 256 KB [n = 8, m = 10000], OK, 20 operations
8 Correct 2 ms 256 KB [n = 8, m = 10000], OK, 20 operations
9 Incorrect 2 ms 384 KB [n = 49, m = 10000] No solution found, but it exists
10 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB [n = 1, m = 10000], OK, 1 operations
2 Correct 2 ms 384 KB [n = 2, m = 10000], OK, 5 operations
3 Correct 2 ms 256 KB [n = 8, m = 10000], OK, 20 operations
4 Correct 2 ms 384 KB [n = 8, m = 10000], OK, 20 operations
5 Correct 2 ms 384 KB [n = 8, m = 10000], OK, 20 operations
6 Correct 2 ms 384 KB [n = 8, m = 10000], OK: No solution
7 Correct 2 ms 256 KB [n = 8, m = 10000], OK, 20 operations
8 Correct 2 ms 256 KB [n = 8, m = 10000], OK, 20 operations
9 Incorrect 2 ms 384 KB [n = 49, m = 10000] No solution found, but it exists
10 Halted 0 ms 0 KB -

Subtask #7
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB [n = 1, m = 10000], OK, 1 operations
2 Correct 2 ms 384 KB [n = 2, m = 10000], OK, 5 operations
3 Correct 2 ms 256 KB [n = 8, m = 10000], OK, 20 operations
4 Correct 2 ms 384 KB [n = 8, m = 10000], OK, 20 operations
5 Correct 2 ms 384 KB [n = 8, m = 10000], OK, 20 operations
6 Correct 2 ms 384 KB [n = 8, m = 10000], OK: No solution
7 Correct 2 ms 256 KB [n = 8, m = 10000], OK, 20 operations
8 Correct 2 ms 256 KB [n = 8, m = 10000], OK, 20 operations
9 Incorrect 2 ms 384 KB [n = 49, m = 10000] No solution found, but it exists
10 Halted 0 ms 0 KB -