Submission #760571

#	Time	Username	Problem	Language	Result	Execution time	Memory
760571		kingfran1907	Parking (CEOI22_parking)	C++14	0 / 100	70 ms	43768 KiB

Main

#include <bits/stdc++.h>
#define X first
#define Y second

using namespace std;
typedef long long llint;

const int maxn = 2e5+10;
const int base = 31337;
const int mod = 1e9+7;
const int inf = 0x3f3f3f3f;
const int logo = 20;
const int off = 1 << logo;
const int treesiz = off << 1;

int n, m;
int niz[maxn][2];
vector< pair<int, int> > pos[maxn];
vector< pair<int, int> > sol;
int nex[maxn], rev[maxn];
bool bio[2 * maxn];
set< int > emps;
vector< int > graph[2 * maxn];
vector< vector< int > > chains, cycles;

void stop() {
	printf("-1\n");
	exit(0);
}

bool istop(pair<int, int> t) {
	int x = t.X;
	int wh = t.Y;
	if (wh == 1 || niz[x][1] == 0) return true;
	return false;
}

void move(int x, int y) {
	//printf("moving: %d %d\n", x + 1, y + 1);
	int ind1 = 0, ind2 = -1;
	if (niz[x][1] != 0) ind1 = 1;
	if (niz[y][0] == 0) ind2 = 0;
	else if (niz[y][1] == 0) ind2 = 1;
	assert(ind2 >= 0 && niz[x][ind1] != 0);

	sol.push_back({x + 1, y + 1});
	if (ind2 == 0) emps.erase(y);
	if (ind1 == 0) emps.insert(x);
	swap(niz[x][ind1], niz[y][ind2]);
}

void calc_pos() {
	emps.clear();
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < 2; j++) {
			if (niz[i][j] != 0) pos[niz[i][j]].push_back({i, j});
		}
		if (niz[i][0] == 0 && niz[i][1] == 0) emps.insert(i);
	}
}

vector< int > get_path(int x) {
	vector< int > v;
	int ptr = x;
	int las = -1;

	while (true) {
		bio[ptr] = true;
		v.push_back(ptr);
		bool flag = false;
		for (int tren : graph[ptr]) {
			if (tren != las && !bio[tren]) {
				las = ptr;
				ptr = tren;
				flag = true;
				break;
			}
		}
		if (!flag) break;
	}
	return v;
}

int price_chain(vector< int > &v) {
	int cnt = 0;
	for (int i = 0; i < v.size(); i += 2) {
		if (!istop({v[i + 1] / 2, v[i + 1] % 2})) cnt++;
	}
	if (cnt <= 1) return 0;

	cnt = 0;
	reverse(v.begin(), v.end());
	for (int i = 0; i < v.size(); i += 2) {
		if (!istop({v[i + 1] / 2, v[i + 1] % 2})) cnt++;
	} 
	reverse(v.begin(), v.end());
	if (cnt <= 1) return 0;
	return 1;
}

void solve_chain(vector< int > &v, int l, int r) {
	//printf("chain solving\n");
	if (l > r) return;
	for (int i = l; i <= r; i += 2) {
		if (v[i] % 2 == 1 && v[i + 1] % 2 == 1) {
			if (emps.empty()) stop();
			int ac = *emps.begin();

			move(v[i] / 2, ac);
			move(v[i + 1] / 2, ac);
			solve_chain(v, l, i - 1);
			solve_chain(v, i + 2, r);
			return;
		}
	}

	for (int i = l; i <= r; i += 2) {
		if (v[i] % 2 == 0 && v[i + 1] % 2 == 0) {
			for (int j = l; j < i; j += 2) 
				move(v[j + 1] / 2, v[j] / 2);
			for (int j = r; j > i + 1; j -= 2) 
				move(v[j - 1] / 2, v[j] / 2);
			move(v[i] / 2, v[i + 1] / 2);
			return;
		}
	}

	if (v[l + 1] % 2 == 1) {
		for (int i = l; i <= r; i += 2) 
			move(v[i + 1] / 2, v[i] / 2);
	} else {
		for (int i = r; i >= l; i -= 2) 
			move(v[i - 1] / 2, v[i] / 2);
	}
} 

inline int get(int x) {
	return niz[x / 2][x % 2];
}

int price_cycle(vector< int > &v) {
	for (int i = 0; i < v.size(); i++) {
		if (get(v[i]) == get(v[(i + 1) % v.size()]) && v[i] % 2 == 1 && v[i + 1] % 2 == 1) {
			vector< int > ne;
			for (int j = 0; j < v.size() - 2; j++) ne.push_back(v[(i + j + 2) % v.size()]);
			return price_chain(ne) + 1;
		}
	}
	return 1;
}

void solve_cycle(vector< int > &v) {
	//printf("cycle solving\n");
	for (int i = 0; i < v.size(); i++) {
		if (get(v[i]) == get(v[(i + 1) % v.size()]) && v[i] % 2 == 1 && v[i + 1] % 2 == 1) {
			vector< int > ne;
			for (int j = 0; j < v.size() - 2; j++) ne.push_back(v[(i + j + 2) % v.size()]);

			if (emps.empty()) stop();
			int x = *emps.begin();
			move(v[i] / 2, x);
			move(v[(i + 1) % v.size()] / 2, x);
			solve_chain(ne, 0, ne.size() - 1);
			return;
		}
	}

	if (emps.empty()) stop();
	int x = *emps.begin();
	int ind = -1;
	for (int i = 0; i < v.size(); i++) {
		if (v[i] % 2 == 1) ind = i;
	}

	move(v[ind] / 2, x);
	for (int i = 0; i < v.size() - 1; i += 2) {
		move(v[(ind + 2 + i) % v.size()] / 2, v[(ind + 1 + i) % v.size()] / 2);
	}
	move(v[(ind + v.size() - 1) % v.size()] / 2, x);
} 

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 0; i < m; i++)
		for (int j = 0; j < 2; j++)
			scanf("%d", &niz[i][j]);
	calc_pos();

	for (int i = 1; i <= n; i++) {
		bool flag = true;
		for (int j = 0; j < 2; j++) {
			int x = pos[i][j].X;
			int y = pos[i][j].Y;
			if (y != 0 || niz[x][1] != 0) flag = false;
		}
		if (flag) move(pos[i][0].X, pos[i][1].Y);
		pos[i].clear();
	}

	calc_pos();
	for (int i = 1; i <= n; i++) {
		int ax = pos[i][0].X;
		int ay = pos[i][0].Y;
		int bx = pos[i][1].X;
		int by = pos[i][1].Y;

		graph[2 * ax + ay].push_back(2 * bx + by);
		graph[2 * bx + by].push_back(2 * ax + ay);
	}
	for (int i = 0; i < m; i++) {
		if (niz[i][0] > 0 && niz[i][1] > 0 && niz[i][0] != niz[i][1]) {
			graph[i * 2].push_back(2 * i + 1);
			graph[i * 2 + 1].push_back(2 * i);
		}
	}

	for (int i = 0; i < 2 * m; i++) {
		if (graph[i].size() == 1 && !bio[i]) {
			vector< int > v = get_path(i);
			if (v.size() == 2) {
				if (v[0] / 2 == v[1] / 2) continue;
				move(v[0] / 2, v[1] / 2);
				continue;
			}
			chains.push_back(v);
		}
	}

	for (int i = 0; i < 2 * m; i++) {
		if (!bio[i] && graph[i].size() == 2) {
			vector< int > v = get_path(i);
			cycles.push_back(v);
		} 
	}

	vector< vector< int > > tr;
	for (auto &iter : chains) {
		if (price_chain(iter) == 0) solve_chain(iter, 0, iter.size() - 1);
		else tr.push_back(iter);
	}
	for (auto &iter : tr) solve_chain(iter, 0, iter.size() - 1);

	tr.clear();
	for (auto &iter : cycles) {
		if (price_cycle(iter) == 1) solve_cycle(iter);
		else tr.push_back(iter);
	}
	for (auto &iter : tr) solve_cycle(iter);

	printf("%d\n", sol.size());
	for (auto iter : sol) printf("%d %d\n", iter.X, iter.Y);
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int price_chain(std::vector<int>&)':
Main.cpp:86:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |  for (int i = 0; i < v.size(); i += 2) {
      |                  ~~^~~~~~~~~~
Main.cpp:93:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |  for (int i = 0; i < v.size(); i += 2) {
      |                  ~~^~~~~~~~~~
Main.cpp: In function 'int price_cycle(std::vector<int>&)':
Main.cpp:142:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |  for (int i = 0; i < v.size(); i++) {
      |                  ~~^~~~~~~~~~
Main.cpp:145:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  145 |    for (int j = 0; j < v.size() - 2; j++) ne.push_back(v[(i + j + 2) % v.size()]);
      |                    ~~^~~~~~~~~~~~~~
Main.cpp: In function 'void solve_cycle(std::vector<int>&)':
Main.cpp:154:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  154 |  for (int i = 0; i < v.size(); i++) {
      |                  ~~^~~~~~~~~~
Main.cpp:157:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  157 |    for (int j = 0; j < v.size() - 2; j++) ne.push_back(v[(i + j + 2) % v.size()]);
      |                    ~~^~~~~~~~~~~~~~
Main.cpp:171:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  171 |  for (int i = 0; i < v.size(); i++) {
      |                  ~~^~~~~~~~~~
Main.cpp:176:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  176 |  for (int i = 0; i < v.size() - 1; i += 2) {
      |                  ~~^~~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:250:11: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wformat=]
  250 |  printf("%d\n", sol.size());
      |          ~^     ~~~~~~~~~~
      |           |             |
      |           int           std::vector<std::pair<int, int> >::size_type {aka long unsigned int}
      |          %ld
Main.cpp:183:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  183 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:186:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  186 |    scanf("%d", &niz[i][j]);
      |    ~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 25
• Subtask 4: 0 / 15
• Subtask 5: 0 / 25
• Subtask 6: 0 / 15