Ideone.com

fork download

#include <iostream>
#include <queue>
#include <map>
#include <vector>
#include <algorithm>
int main () {
	std::queue<std::vector<int>> que;
	std::map<std::vector<int>, int> dist;
	std::map<std::vector<int>, std::vector<int>> par;
	size_t sz;
	std::cin >> sz;
	std::vector<int> st(sz);
	int n = 0;
	for(size_t i = 0;i<sz;i++) {
		std::cin >> st[i];
		n=std::max(n, st[i]);
	}
	que.push(st);
	dist[st]=0;
	reverse(st.begin(), st.end());
	int ls=0;
	while(que.size()) {
		auto at = que.front();
		que.pop();
		{
			auto rev = at;
			std::reverse(rev.begin(), rev.end());
			if(dist.find(rev)!=dist.end()) {
				std::cout << dist[rev]+dist[at] << std::endl;
				std::vector<std::vector<int>> res;
				while(at.size()) {
					res.push_back(at);
					at=par[at];
				}
				std::reverse(res.begin(), res.end());
				rev=par[rev];
				while(rev.size()) {
					std::reverse(rev.begin(), rev.end());
					res.push_back(rev);
					std::reverse(rev.begin(), rev.end());
					rev=par[rev];
				}
				for(auto i:res) {
					for(int j:i)std::cout << j << " ";
					std::cout << "\n";
				}
				return 0;
			}
		}
		bool used[n+1];
		for(int i = 0;i<=n;i++)used[i]=0;
		for(size_t j = 0;j<at.size();j++)used[at[j]]=1;
		for(size_t j = 0;j<at.size();j++) {
			if(at[j]) {
				for(int k = 1;k<at[j];k++) {
					if(used[k] or used[at[j]-k] or at[j]-k==k)continue;
					std::vector<int> tmp;
					for(size_t m = 0;m<j;m++)tmp.push_back(at[m]);
					tmp.push_back(k);
					tmp.push_back(at[j]-k);
					for(size_t m = j+1;m<at.size();m++)tmp.push_back(at[m]);
					if(dist.find(tmp)!=dist.end())continue;
					dist[tmp]=dist[at]+1;
					par[tmp]=at;
					que.push(tmp);
				}
			}
		}
		for(size_t j = 0;j+1<at.size();j++) {
			if(at[j]+at[j+1]<=n and used[at[j]+at[j+1]]==0) {
				std::vector<int> tmp;
				for(size_t m = 0;m<j;m++)tmp.push_back(at[m]);
				tmp.push_back(at[j]+at[j+1]);
				for(size_t m = j+2;m<at.size();m++)tmp.push_back(at[m]);
				if(dist.find(tmp)!=dist.end())continue;
				dist[tmp]=dist[at]+1;
				par[tmp]=at;
				que.push(tmp);
			}
		}
	}
	return 0;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8cXVldWU+CiNpbmNsdWRlIDxtYXA+CiNpbmNsdWRlIDx2ZWN0b3I+CiNpbmNsdWRlIDxhbGdvcml0aG0+CmludCBtYWluICgpIHsKCXN0ZDo6cXVldWU8c3RkOjp2ZWN0b3I8aW50Pj4gcXVlOwoJc3RkOjptYXA8c3RkOjp2ZWN0b3I8aW50PiwgaW50PiBkaXN0OwoJc3RkOjptYXA8c3RkOjp2ZWN0b3I8aW50Piwgc3RkOjp2ZWN0b3I8aW50Pj4gcGFyOwoJc2l6ZV90IHN6OwoJc3RkOjpjaW4gPj4gc3o7CglzdGQ6OnZlY3RvcjxpbnQ+IHN0KHN6KTsKCWludCBuID0gMDsKCWZvcihzaXplX3QgaSA9IDA7aTxzejtpKyspIHsKCQlzdGQ6OmNpbiA+PiBzdFtpXTsKCQluPXN0ZDo6bWF4KG4sIHN0W2ldKTsKCX0KCXF1ZS5wdXNoKHN0KTsKCWRpc3Rbc3RdPTA7CglyZXZlcnNlKHN0LmJlZ2luKCksIHN0LmVuZCgpKTsKCWludCBscz0wOwoJd2hpbGUocXVlLnNpemUoKSkgewoJCWF1dG8gYXQgPSBxdWUuZnJvbnQoKTsKCQlxdWUucG9wKCk7CgkJewoJCQlhdXRvIHJldiA9IGF0OwoJCQlzdGQ6OnJldmVyc2UocmV2LmJlZ2luKCksIHJldi5lbmQoKSk7CgkJCWlmKGRpc3QuZmluZChyZXYpIT1kaXN0LmVuZCgpKSB7CgkJCQlzdGQ6OmNvdXQgPDwgZGlzdFtyZXZdK2Rpc3RbYXRdIDw8IHN0ZDo6ZW5kbDsKCQkJCXN0ZDo6dmVjdG9yPHN0ZDo6dmVjdG9yPGludD4+IHJlczsKCQkJCXdoaWxlKGF0LnNpemUoKSkgewoJCQkJCXJlcy5wdXNoX2JhY2soYXQpOwoJCQkJCWF0PXBhclthdF07CgkJCQl9CgkJCQlzdGQ6OnJldmVyc2UocmVzLmJlZ2luKCksIHJlcy5lbmQoKSk7CgkJCQlyZXY9cGFyW3Jldl07CgkJCQl3aGlsZShyZXYuc2l6ZSgpKSB7CgkJCQkJc3RkOjpyZXZlcnNlKHJldi5iZWdpbigpLCByZXYuZW5kKCkpOwoJCQkJCXJlcy5wdXNoX2JhY2socmV2KTsKCQkJCQlzdGQ6OnJldmVyc2UocmV2LmJlZ2luKCksIHJldi5lbmQoKSk7CgkJCQkJcmV2PXBhcltyZXZdOwoJCQkJfQoJCQkJZm9yKGF1dG8gaTpyZXMpIHsKCQkJCQlmb3IoaW50IGo6aSlzdGQ6OmNvdXQgPDwgaiA8PCAiICI7CgkJCQkJc3RkOjpjb3V0IDw8ICJcbiI7CgkJCQl9CgkJCQlyZXR1cm4gMDsKCQkJfQoJCX0KCQlib29sIHVzZWRbbisxXTsKCQlmb3IoaW50IGkgPSAwO2k8PW47aSsrKXVzZWRbaV09MDsKCQlmb3Ioc2l6ZV90IGogPSAwO2o8YXQuc2l6ZSgpO2orKyl1c2VkW2F0W2pdXT0xOwoJCWZvcihzaXplX3QgaiA9IDA7ajxhdC5zaXplKCk7aisrKSB7CgkJCWlmKGF0W2pdKSB7CgkJCQlmb3IoaW50IGsgPSAxO2s8YXRbal07aysrKSB7CgkJCQkJaWYodXNlZFtrXSBvciB1c2VkW2F0W2pdLWtdIG9yIGF0W2pdLWs9PWspY29udGludWU7CgkJCQkJc3RkOjp2ZWN0b3I8aW50PiB0bXA7CgkJCQkJZm9yKHNpemVfdCBtID0gMDttPGo7bSsrKXRtcC5wdXNoX2JhY2soYXRbbV0pOwoJCQkJCXRtcC5wdXNoX2JhY2soayk7CgkJCQkJdG1wLnB1c2hfYmFjayhhdFtqXS1rKTsKCQkJCQlmb3Ioc2l6ZV90IG0gPSBqKzE7bTxhdC5zaXplKCk7bSsrKXRtcC5wdXNoX2JhY2soYXRbbV0pOwoJCQkJCWlmKGRpc3QuZmluZCh0bXApIT1kaXN0LmVuZCgpKWNvbnRpbnVlOwoJCQkJCWRpc3RbdG1wXT1kaXN0W2F0XSsxOwoJCQkJCXBhclt0bXBdPWF0OwoJCQkJCXF1ZS5wdXNoKHRtcCk7CgkJCQl9CgkJCX0KCQl9CgkJZm9yKHNpemVfdCBqID0gMDtqKzE8YXQuc2l6ZSgpO2orKykgewoJCQlpZihhdFtqXSthdFtqKzFdPD1uIGFuZCB1c2VkW2F0W2pdK2F0W2orMV1dPT0wKSB7CgkJCQlzdGQ6OnZlY3RvcjxpbnQ+IHRtcDsKCQkJCWZvcihzaXplX3QgbSA9IDA7bTxqO20rKyl0bXAucHVzaF9iYWNrKGF0W21dKTsKCQkJCXRtcC5wdXNoX2JhY2soYXRbal0rYXRbaisxXSk7CgkJCQlmb3Ioc2l6ZV90IG0gPSBqKzI7bTxhdC5zaXplKCk7bSsrKXRtcC5wdXNoX2JhY2soYXRbbV0pOwoJCQkJaWYoZGlzdC5maW5kKHRtcCkhPWRpc3QuZW5kKCkpY29udGludWU7CgkJCQlkaXN0W3RtcF09ZGlzdFthdF0rMTsKCQkJCXBhclt0bXBdPWF0OwoJCQkJcXVlLnB1c2godG1wKTsKCQkJfQoJCX0KCX0KCXJldHVybiAwOwp9Cg==

Success #stdin #stdout 1.1s 97604KB

stdin

12 
6 11 8 2 7 10 9 12 4 1 14 3

stdout

172
6 11 8 2 7 10 9 12 4 1 14 3 
6 11 8 2 7 10 9 12 5 14 3 
6 11 8 2 7 10 9 12 1 4 14 3 
6 11 8 2 7 10 9 13 4 14 3 
5 1 11 8 2 7 10 9 13 4 14 3 
5 12 8 2 7 10 9 13 4 14 3 
5 12 8 2 6 1 10 9 13 4 14 3 
5 12 8 2 6 11 9 13 4 14 3 
5 12 10 6 11 9 13 4 14 3 
5 12 2 8 6 11 9 13 4 14 3 
5 12 2 8 6 1 10 9 13 4 14 3 
5 12 2 8 7 10 9 13 4 14 3 
5 1 11 2 8 7 10 9 13 4 14 3 
6 11 2 8 7 10 9 13 4 14 3 
6 11 2 8 7 10 9 12 1 4 14 3 
6 13 8 7 10 9 12 1 4 14 3 
6 13 8 7 10 9 12 5 14 3 
6 13 8 7 10 9 12 5 14 1 2 
6 13 8 3 4 10 9 12 5 14 1 2 
6 13 11 4 10 9 12 5 14 1 2 
6 13 11 4 10 9 12 5 14 3 
6 13 11 4 2 8 9 12 5 14 3 
6 13 11 4 2 7 1 9 12 5 14 3 
6 13 11 4 2 7 10 12 5 14 3 
6 13 11 4 9 10 12 5 14 3 
6 13 11 4 9 10 12 5 14 1 2 
6 13 8 3 4 9 10 12 5 14 1 2 
6 13 8 7 9 10 12 5 14 1 2 
6 13 8 7 9 10 12 5 14 3 
6 2 11 8 7 9 10 12 5 14 3 
6 2 11 8 7 9 10 12 1 4 14 3 
6 2 11 8 7 9 10 13 4 14 3 
6 2 11 8 7 9 10 1 12 4 14 3 
6 13 8 7 9 10 1 12 4 14 3 
6 13 8 2 5 9 10 1 12 4 14 3 
6 13 8 2 5 9 11 12 4 14 3 
6 13 10 5 9 11 12 4 14 3 
6 13 10 5 9 11 12 4 14 1 2 
6 13 7 3 5 9 11 12 4 14 1 2 
6 13 7 8 9 11 12 4 14 1 2 
6 13 7 8 9 11 12 4 14 3 
5 1 13 7 8 9 11 12 4 14 3 
5 1 13 7 8 9 11 10 2 4 14 3 
5 1 13 7 8 9 11 10 6 14 3 
5 1 13 7 8 9 11 10 6 2 12 3 
5 14 7 8 9 11 10 6 2 12 3 
5 13 1 7 8 9 11 10 6 2 12 3 
5 13 1 7 8 9 11 10 6 14 3 
5 13 1 7 8 9 11 10 2 4 14 3 
5 13 1 7 8 9 11 12 4 14 3 
5 13 1 7 2 6 9 11 12 4 14 3 
5 13 8 2 6 9 11 12 4 14 3 
5 13 10 6 9 11 12 4 14 3 
5 13 10 6 1 8 11 12 4 14 3 
5 13 10 7 8 11 12 4 14 3 
5 13 10 7 2 6 11 12 4 14 3 
5 13 10 9 6 11 12 4 14 3 
5 13 10 1 8 6 11 12 4 14 3 
5 13 10 1 8 6 2 9 12 4 14 3 
5 13 11 8 6 2 9 12 4 14 3 
5 13 11 1 7 6 2 9 12 4 14 3 
5 13 11 1 7 8 9 12 4 14 3 
5 13 11 1 7 8 9 2 10 4 14 3 
5 13 12 7 8 9 2 10 4 14 3 
5 13 12 7 8 11 10 4 14 3 
5 13 12 7 2 6 11 10 4 14 3 
5 13 12 9 6 11 10 4 14 3 
5 13 12 9 6 11 2 8 4 14 3 
5 13 12 9 6 1 10 2 8 4 14 3 
5 13 12 9 7 10 2 8 4 14 3 
5 13 1 11 9 7 10 2 8 4 14 3 
5 13 1 11 9 7 12 8 4 14 3 
5 13 1 11 9 7 2 10 8 4 14 3 
5 13 1 11 9 7 2 10 12 14 3 
5 13 1 11 9 7 2 10 12 6 8 3 
5 14 11 9 7 2 10 12 6 8 3 
5 1 13 11 9 7 2 10 12 6 8 3 
5 1 13 11 9 7 2 10 12 14 3 
6 13 11 9 7 2 10 12 14 3 
6 13 11 1 8 7 2 10 12 14 3 
6 13 11 1 8 9 10 12 14 3 
6 13 11 1 8 9 10 5 7 14 3 
6 13 12 8 9 10 5 7 14 3 
6 11 2 12 8 9 10 5 7 14 3 
6 11 2 12 8 9 10 5 7 13 1 3 
6 11 14 8 9 10 5 7 13 1 3 
6 11 14 8 9 10 12 13 1 3 
6 11 14 8 2 7 10 12 13 1 3 
6 11 14 8 2 7 10 12 13 4 
6 11 14 8 2 7 10 3 9 13 4 
6 11 14 8 2 7 10 3 9 12 1 4 
6 11 14 8 2 7 13 9 12 1 4 
6 11 14 10 7 13 9 12 1 4 
6 11 14 10 7 13 9 12 5 
6 11 14 10 7 13 8 1 12 5 
6 11 14 10 7 9 4 8 1 12 5 
6 11 14 10 7 9 4 8 13 5 
6 11 14 10 7 9 12 13 5 
2 4 11 14 10 7 9 12 13 5 
2 1 3 11 14 10 7 9 12 13 5 
2 1 3 11 6 8 10 7 9 12 13 5 
2 1 14 6 8 10 7 9 12 13 5 
3 14 6 8 10 7 9 12 13 5 
3 14 4 2 8 10 7 9 12 13 5 
3 14 4 2 8 10 1 6 9 12 13 5 
3 14 4 2 8 11 6 9 12 13 5 
3 14 4 10 11 6 9 12 13 5 
3 14 4 10 11 6 2 7 12 13 5 
3 14 4 10 11 8 7 12 13 5 
3 14 4 10 2 9 8 7 12 13 5 
3 14 4 10 2 9 8 7 1 11 13 5 
3 14 4 12 9 8 7 1 11 13 5 
3 14 4 12 9 2 6 7 1 11 13 5 
3 14 4 12 9 2 6 8 11 13 5 
3 14 4 12 9 2 6 8 1 10 13 5 
3 14 4 12 11 6 8 1 10 13 5 
3 14 4 12 11 6 9 10 13 5 
3 14 4 12 11 6 2 7 10 13 5 
3 14 4 12 11 8 7 10 13 5 
3 14 4 12 11 8 1 6 10 13 5 
3 14 4 12 11 9 6 10 13 5 
3 14 4 12 11 9 6 2 8 13 5 
3 14 4 12 11 9 6 2 7 1 13 5 
3 14 4 12 11 9 8 7 1 13 5 
3 14 4 2 10 11 9 8 7 1 13 5 
3 14 6 10 11 9 8 7 1 13 5 
3 12 2 6 10 11 9 8 7 1 13 5 
3 12 2 6 10 11 9 8 7 14 5 
3 12 2 6 10 11 9 8 7 13 1 5 
3 14 6 10 11 9 8 7 13 1 5 
3 14 4 2 10 11 9 8 7 13 1 5 
3 14 4 12 11 9 8 7 13 1 5 
3 14 4 12 11 9 8 7 13 6 
2 1 14 4 12 11 9 8 7 13 6 
2 1 14 4 12 11 9 5 3 7 13 6 
2 1 14 4 12 11 9 5 10 13 6 
3 14 4 12 11 9 5 10 13 6 
3 14 4 12 11 9 5 2 8 13 6 
3 14 4 12 1 10 9 5 2 8 13 6 
3 14 4 12 1 10 9 7 8 13 6 
3 14 4 12 1 10 9 7 8 11 2 6 
3 14 4 13 10 9 7 8 11 2 6 
3 14 4 1 12 10 9 7 8 11 2 6 
3 14 5 12 10 9 7 8 11 2 6 
3 14 5 12 10 9 7 8 13 6 
2 1 14 5 12 10 9 7 8 13 6 
2 1 14 5 12 10 9 4 3 8 13 6 
2 1 14 5 12 10 9 4 11 13 6 
3 14 5 12 10 9 4 11 13 6 
3 14 5 12 10 7 2 4 11 13 6 
3 14 5 12 9 1 7 2 4 11 13 6 
3 14 5 12 9 8 2 4 11 13 6 
3 14 5 12 9 10 4 11 13 6 
2 1 14 5 12 9 10 4 11 13 6 
2 1 14 5 12 9 10 4 3 8 13 6 
2 1 14 5 12 9 10 7 8 13 6 
3 14 5 12 9 10 7 8 13 6 
3 14 4 1 12 9 10 7 8 13 6 
3 14 4 1 12 9 10 7 8 2 11 6 
3 14 4 13 9 10 7 8 2 11 6 
3 14 4 13 9 10 7 8 2 11 1 5 
3 14 4 13 9 10 7 8 2 12 5 
3 14 4 13 9 10 1 6 8 2 12 5 
3 14 4 13 9 11 6 8 2 12 5 
3 14 4 13 9 11 6 10 12 5 
3 14 4 13 9 11 6 2 8 12 5 
3 14 4 13 9 10 1 6 2 8 12 5 
3 14 4 13 9 10 7 2 8 12 5 
3 14 4 13 9 10 7 2 8 11 1 5 
3 14 4 13 9 10 7 2 8 11 6 
3 14 4 1 12 9 10 7 2 8 11 6 
3 14 5 12 9 10 7 2 8 11 6 
3 14 1 4 12 9 10 7 2 8 11 6

https://ideone.com/MGFwdo

language:

C++14 (gcc 8.3)

created:

visibility:

secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!

Discover > Sphere Engine API

Discover > IDE Widget

Choose your language