제출 #805770

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
805770		YesPy	Cutting a rectangle (LMIO18_staciakampis)	C++17	0 / 100	1079 ms	312 KiB

staciakampis

#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops")

#define ff first
#define ss second
#define tcT template<class T
#define fastio ios::sync_with_stdio(false);cin.tie(nullptr);
#define ln '\n'
#define nwln cout<<ln;

using namespace std;

tcT> using vr = vector<T>;
using pi = pair<int, int>;
using vi = vr<int>;
using vpi = vr<pi>;
using ll = long long;
using oo = bool;

#define maxs(i, j) (i = max(i, j))
#define fri(i,a,b) for(int i=(a); i<(b); ++i)
#define each(x, a) for(auto& x: a)

#define sz(x) int((x).size())
#define bg(x) begin(x)
#define all(x) bg(x), end(x)
#define sr(x) sort(all(x))
#define phb push_back
#define ppb pop_back
#define eb emplace_back

const int MX = (int) 3e5+3;
int K;
set<int> ans;
vpi config;

inline void go(vpi rec) {
	// cout<<"New instance of GO"<<ln;
	// each(x, rec) cout<<x.ff<<", "<<x.ss<<ln;
	// nwln

	if(sz(rec) == 1) ans.insert(min(rec[0].ff, rec[0].ss));

	pi t[2];
	t[0] = rec.back(), rec.ppb();
	t[1] = rec.back(), rec.ppb();

	pi flag[2];
	flag[0] = flag[1] = {-1, -1};

	if(t[0].ff == t[1].ff) {
		flag[0] = {t[0].ff, t[0].ss + t[1].ss};
		if(flag[0].ff < flag[0].ss) swap(flag[0].ff, flag[0].ss);
	}

	if(t[0].ss == t[1].ss) {
		flag[1] = {t[0].ff + t[1].ff, t[0].ss};
		if(flag[1].ff < flag[1].ss) swap(flag[1].ff, flag[1].ss);
	}

	if(flag[0].ff != -1) {
		rec.eb(flag[0]);
		go(rec);
		rec.ppb();
	}

	if(flag[1].ff != -1) {
		rec.eb(flag[1]);
		go(rec);
		rec.ppb();
	}

	swap(t[1].ff, t[1].ss);
	flag[0] = flag[1] = {-1, -1};

	if(t[0].ff == t[1].ff) {
		flag[0] = {t[0].ff, t[0].ss + t[1].ss};
		if(flag[0].ff < flag[0].ss) swap(flag[0].ff, flag[0].ss);
	}

	if(t[0].ss == t[1].ss) {
		flag[1] = {t[0].ff + t[1].ff, t[0].ss};
		if(flag[1].ff < flag[1].ss) swap(flag[1].ff, flag[1].ss);
	}

	if(flag[0].ff != -1) {
		rec.eb(flag[0]);
		go(rec);
		rec.ppb();
	}

	if(flag[1].ff != -1) {
		rec.eb(flag[1]);
		go(rec);
		rec.ppb();
	}
}

int main()
{
	fastio
	cin>>K;

	while(K--) {
		int a, b;
		cin>>a>>b;
		config.eb(a, b);
	}

	do {
		go(config);
	} while(next_permutation(all(config)));

	cout<<sz(ans)<<ln;
	each(x, ans) cout<<x<<ln;

	return 0;
}

/*
For subtask 2 basically is the following:

For each DIV divisor of SUM := a1+...+ak, check if it's possible to partition
the set {a1, ..., ak} into subsets having sum = DIV

If it's possible, print min(DIV, SUM/DIV)
But idk how to do it efficiently, yet!
*/

• Subtask 1: 0 / 25
• Subtask 2: 0 / 20
• Subtask 3: 0 / 55