Submission #223216

#	Time	Username	Problem	Language	Result	Execution time	Memory
223216		spacewalker	Remittance (JOI19_remittance)	C++14	15 / 100	14 ms	5376 KiB

remittance

#include <bits/stdc++.h>

using namespace std;

int encode(vector<int> &pos) {
	int ans = 0;
	for (int i = (int)pos.size() - 1; i >= 0; --i) ans = ans * 8 + pos[i];
	return 8 * ans + pos.size();
}

vector<int> decode(int encoded) {
	vector<int> ans(encoded % 8);
	encoded /= 8;
	for (int i = 0; i < ans.size(); ++i) {
		ans[i] = encoded % 8;
		encoded /= 8;
	}
	return ans;
}

vector<int> nextStates(int curState) {
	vector<int> status = decode(curState);
	int n = status.size();
	vector<int> ans;
	for (int i = 0; i < status.size(); ++i) {
		if (status[i] >= 2) {
			status[i] -= 2; status[(i + 1) % n]++;
			ans.push_back(encode(status));
			status[i] += 2; status[(i + 1) % n]--;
		}
	}
	return ans;
}

int main() {
	int n; scanf("%d", &n);
	vector<int> before(n), after(n);
	for (int i = 0; i < n; ++i) scanf("%d %d", &before[i], &after[i]);
	vector<bool> visited(20000000);
	int start = encode(before);
	int end = encode(after);
	visited[start] = true;
	queue<int> q;
	q.push(start);
	while (!q.empty()) {
		int cur = q.front(); q.pop();
//		printf("state reached:\n");
//		vector<int> cslist = decode(cur);
//		for (int x : cslist) printf("%d ", x);
//		printf("\n");
		vector<int> pnext = nextStates(cur);
		for (int x : pnext) {
			if (!visited[x]) {
				visited[x] = true;
				q.push(x);
			}
		}
	}
	if (visited[end]) printf("Yes\n");
	else printf("No\n");
	return 0;
}

Compilation message (stderr)

remittance.cpp: In function 'std::vector<int> decode(int)':
remittance.cpp:14:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < ans.size(); ++i) {
                  ~~^~~~~~~~~~~~
remittance.cpp: In function 'std::vector<int> nextStates(int)':
remittance.cpp:25:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < status.size(); ++i) {
                  ~~^~~~~~~~~~~~~~~
remittance.cpp: In function 'int main()':
remittance.cpp:36:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int n; scanf("%d", &n);
         ~~~~~^~~~~~~~~~
remittance.cpp:38:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 0; i < n; ++i) scanf("%d %d", &before[i], &after[i]);
                              ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 0 / 40
• Subtask 3: 0 / 45