Submission #699373

#	Time	Username	Problem	Language	Result	Execution time	Memory
699373		flappybird	Shuffle (NOI19_shuffle)	C++17	48 / 100	2 ms	596 KiB

shuffle

#include "shuffle.h"
#include <bits/stdc++.h>
#include <cassert>
using namespace std;

typedef pair<int, int> pii;

#define MAX 1010

vector<int> adj[MAX];

pii v2p(vector<int> v) {
	return pii(min(v[0], v[1]), max(v[0], v[1]));
}

int cnt;
int vis[MAX];
int ord[MAX];
int rev[MAX];

void dfs(int x) {
	if (vis[x]) return;
	vis[x] = 1;
	ord[++cnt] = x;
	for (auto v : adj[x]) dfs(v);
}

vector<vector<int>> listall;
vector<vector<int>> tree[MAX];

int countall(int ind, vector<int>& v) {
	int cnt = 0;
	for (auto x : v) {
		int i = lower_bound(listall[ind].begin(), listall[ind].end(), x) - listall[ind].begin();
		if (i < listall[ind].size() && listall[ind][i] == x) cnt++;
	}
	return cnt;
}

vector<int> getsubset(vector<int>& v1, vector<int>& v2) {
	sort(v1.begin(), v1.end());
	sort(v2.begin(), v2.end());
	vector<int> v;
	for (auto x : v1) {
		int ind = lower_bound(v2.begin(), v2.end(), x) - v2.begin();
		if (ind < v2.size() && v2[ind] == x) v.push_back(x);
	}
	return v;
}

// kth
int base3(int n, int k) {
	while (k--) n /= 3;
	return n % 3;
}

int top[MAX];
int pow3[10] = { 1, 3, 9, 27, 81, 243, 729 };

vector<int> solve(int N, int B, int K, int Q, int ST) {
	if (K == 2) {
		vector<vector<int>> vs;
		int i;
		vector<int> v;
		set<pii> vpi;
		for (i = 0; i < N; i++) {
			v.push_back(i + 1);
			if (v.size() >= 2) {
				vs.push_back(v);
				v.clear();
			}
		}
		auto res = shuffle(vs);
		vs.clear();
		for (auto& v : res) {
			vpi.emplace(v2p(v));
			adj[v[0]].push_back(v[1]);
			adj[v[1]].push_back(v[0]);
		}
		for (i = 0; i < N; i++) {
			v.push_back(((i + 1) % N) + 1);
			if (v.size() >= 2) {
				vs.push_back(v);
				v.clear();
			}
		}
		res = shuffle(vs);
		vs.clear();
		for (auto& v : res) {
			adj[v[0]].push_back(v[1]);
			adj[v[1]].push_back(v[0]);
		}
		vs.push_back({ 1, 2 });
		for (i = 2; i <= N / 2; i++) vs.push_back({ i + 1, i + 1 + N / 2 - 1 });
		res = shuffle(vs);
		vs.clear();
		pii p = pii(0, 0);
		for (auto& v : res) if (vpi.find(v2p(v)) != vpi.end()) p = v2p(v);
		auto [z, o] = p;
		set<pii> newset;
		for (i = 4; i < N; i++) {
			v.push_back(i + 1);
			if (v.size() >= 2) {
				vs.push_back(v);
				v.clear();
			}
		}
		vs.push_back({ 1, 3 });
		vs.push_back({ 2, 4 });
		res = shuffle(vs);
		for (auto& v : res) newset.insert(v2p(v));
		cnt = 1;
		vis[z] = 1;
		ord[1] = z;
		dfs(o);
		if (newset.find(pii(min(ord[1], ord[3]), max(ord[1], ord[3]))) == newset.end()) {
			memset(vis, 0, sizeof(vis));
			cnt = 1;
			swap(z, o);
			vis[z] = 1;
			ord[1] = z;
			dfs(o);
		}
		vector<int> ans;
		for (i = 1; i <= N; i++) ans.push_back(ord[i]);
		return ans;
	}
	else if (B == 2) {
		vector<vector<int>> vs;
		vector<int> v;
		int i;
		for (i = 1; i <= N; i++) {
			v.push_back(i);
			if (v.size() >= K) vs.push_back(v), v.clear();
		}
		auto res = shuffle(vs);
		swap(vs[0].back(), vs[1].back());
		auto res1 = shuffle(vs);
		swap(vs[0].back(), vs[1].back());
		swap(vs[0].back(), vs[1][0]);
		auto res2 = shuffle(vs);
		swap(vs[0].back(), vs[1][0]);
		if (getsubset(res[0], res1[0]).size() > 1) swap(res1[0], res1[1]);
		int i1, i2;
		i1 = getsubset(res1[0], res[0])[0];
		i2 = getsubset(res1[1], res[1])[0];
		int ii1, ii2;
		if (getsubset(res[0], res2[0]).size() > 1) swap(res2[0], res2[1]);
		ii1 = getsubset(res2[0], res[0])[0];
		ii2 = getsubset(res2[1], res[1])[0];
		if (i2 == ii1 || i2 == ii2) swap(i1, i2), swap(res[0], res[1]), swap(vs[0], vs[1]);
		int k;
		ord[K] = i1;
		ord[K * 2] = i2;
		for (auto v : res[1]) rev[v] += K;
		for (k = 0; k < 9; k++) {
			for (i = 0; i < K - 1; i++) if ((i + 1) >> k & 1) swap(vs[0][i], vs[1][i]);
			res = shuffle(vs);
			int c = 0;
			for (auto v : res[0]) if (v == i1) c = 1;
			if (!c) swap(res[0], res[1]);
			for (auto v : res[0]) if (rev[v] >= K) rev[v] += 1 << k;
			for (auto v : res[1]) if (rev[v] < K) rev[v] += 1 << k;
			for (i = 0; i < K - 1; i++) if ((i + 1) >> k & 1) swap(vs[0][i], vs[1][i]);
		}
		for (i = 1; i <= N; i++) if (!ord[rev[i]]) ord[rev[i]] = i;
		vector<int> ansv;
		for (i = 1; i <= N; i++) ansv.push_back(ord[i]);
		return ansv;
	}
	else {
		int i;
		vector<vector<int>> vs;
		vector<int> v;
		for (i = 1; i <= N; i++) {
			v.push_back(i);
			if (v.size() >= K) vs.push_back(v), v.clear();
		}
		auto res = shuffle(vs);
		int e0 = vs[0].back();
		vs[0].pop_back();
		for (i = B - 1; i > 0; i--) {
			vs[(i + 1) % B].push_back(vs[i].back());
			vs[i].pop_back();
		}
		vs[1].push_back(e0);
		auto res2 = shuffle(vs);
		vs[1].pop_back();
		for (i = 1; i < B; i++) {
			vs[i].push_back(vs[(i + 1) % B].back());
			vs[(i + 1) % B].pop_back();
		}
		vs[0].push_back(e0);
		for (i = 1; i < B - 1; i++) swap(vs[i].back(), vs[i + 1].back());
		for (i = B - 2; i > 0; i--) swap(vs[i].back(), vs[i + 1].back());
		auto res3 = shuffle(vs);
		set<vector<int>> st;
		for (auto& v : res) sort(v.begin(), v.end());
		for (auto& v : res3) sort(v.begin(), v.end());
		for (auto& v : res3) st.insert(v);
		int ind = -1;
		for (i = 0; i < B; i++) {
			if (st.find(res[i]) != st.end()) {
				ind = i;
				break;
			}
		}
		assert(ind != -1);
		vector<int> inds;
		swap(res[ind], res[0]);
		for (i = 0; i < B; i++) {
			int k;
			int n = -1;
			for (k = 0; k < B; k++) {
				auto v = getsubset(res2[k], res[i]);
				if (v.size() == 1) {
					inds.push_back(v[0]);
					n = k;
					break;
				}
			}
			for (k = 0; k < B; k++) {
				auto v = getsubset(res2[n], res[k]);
				if (v.size() == K - 1) {
					swap(res[(i + 1) % B], res[k]);
					break;
				}
			}
		}
		for (i = 1; i < B; i++) for (auto v : res[i]) rev[v] = K * i, top[v] = i;
		for (i = 0; i < B; i++) ord[K * i + K] = inds[i];
		int j, k;
		for (k = 0; k < 6; k++) {
			vector<vector<int>> nvs(B);
			for (i = 0; i < B; i++) for (j = 0; j < K - 1; j++) nvs[(i + base3(j + 1, k)) % B].push_back(vs[i][j]);
			for (i = 0; i < B; i++) nvs[i].push_back(i * K + K);
			auto res = shuffle(nvs);
			for (i = 0; i < B; i++) {
				for (int j = i; j < B; j++) {
					int c = 0;
					for (auto v : res[j]) if (v == inds[i]) c = 1;
					if (c) {
						swap(res[i], res[j]);
						break;
					}
				}
			}
			for (i = 0; i < B; i++) {
				for (auto v : res[i]) {
					int del = (i - top[v] + B) % B;
					rev[v] += del * pow3[k];
				}
			}
		}
		for (i = 1; i <= N; i++) if (!ord[rev[i]]) ord[rev[i]] = i;
		vector<int> ansv;
		for (i = 1; i <= N; i++) ansv.push_back(ord[i]), assert(ord[i]);
		return ansv;
	}
}

Compilation message (stderr)

shuffle.cpp: In function 'int countall(int, std::vector<int>&)':
shuffle.cpp:35:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |   if (i < listall[ind].size() && listall[ind][i] == x) cnt++;
      |       ~~^~~~~~~~~~~~~~~~~~~~~
shuffle.cpp: In function 'std::vector<int> getsubset(std::vector<int>&, std::vector<int>&)':
shuffle.cpp:46:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |   if (ind < v2.size() && v2[ind] == x) v.push_back(x);
      |       ~~~~^~~~~~~~~~~
shuffle.cpp: In function 'std::vector<int> solve(int, int, int, int, int)':
shuffle.cpp:134:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  134 |    if (v.size() >= K) vs.push_back(v), v.clear();
      |        ~~~~~~~~~^~~~
shuffle.cpp:177:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  177 |    if (v.size() >= K) vs.push_back(v), v.clear();
      |        ~~~~~~~~~^~~~
shuffle.cpp:224:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  224 |     if (v.size() == K - 1) {
      |         ~~~~~~~~~^~~~~~~~

• Subtask 1: 2 / 2
• Subtask 2: 3 / 3
• Subtask 3: 12 / 12
• Subtask 4: 16 / 16
• Subtask 5: 15 / 15
• Subtask 6: 0 / 52