Submission #260389

#	Time	Username	Problem	Language	Result	Execution time	Memory
260389		patrikpavic2	Lamps (JOI19_lamps)	C++17	6 / 100	262 ms	8440 KiB

lamp

#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

const int N = 1e6 + 500;

int dis[N], n, A, B;
queue < int > Q;

int main(){
	memset(dis, -1, sizeof(dis));
	scanf("%d", &n);
	for(int i = 0;i < n;i++){
		char c; scanf(" %c", &c);
		A += (1 << i) * (c - '0');
	}
	for(int i = 0;i < n;i++){
		char c; scanf(" %c", &c);
		B += (1 << i) * (c - '0');
	}
	dis[A] = 0; Q.push(A);
	for(;!Q.empty();Q.pop()){
		int cur = Q.front();
		for(int l = 0;l < n;l++){
			int t1 = cur, t2 = cur, t3 = cur;
			for(int r = l;r < n;r++){
				t1 &= (1 << n) - (1 << r) - 1;
				t2 |= (1 << r);
				t3 ^= (1 << r);
				if(dis[t1] == -1){
					dis[t1] = dis[cur] + 1;
					Q.push(t1);
				}
				if(dis[t2] == -1){
					dis[t2] = dis[cur] + 1;
					Q.push(t2);
				}
				if(dis[t3] == -1){
					dis[t3] = dis[cur] + 1;
					Q.push(t3);
				}
			}
		}
	}
	printf("%d\n", dis[B]);
}

Compilation message (stderr)

lamp.cpp: In function 'int main()':
lamp.cpp:14:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
lamp.cpp:16:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   char c; scanf(" %c", &c);
           ~~~~~^~~~~~~~~~~
lamp.cpp:20:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   char c; scanf(" %c", &c);
           ~~~~~^~~~~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 0 / 41
• Subtask 3: 0 / 4
• Subtask 4: 0 / 49