oj.uz

Submission #805778

# Submission time Handle Problem Language Result Execution time Memory
805778 2023-08-03T23:14:36 Z YesPy Cutting a rectangle (LMIO18_staciakampis) C++17
0 / 100
 826 ms 262144 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops")
#pragma inline_recursion(on)
// #pragma GCC optimize("O2")
// #pragma GCC optimize("Ofast")

#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;

time_t xd1, xd2;

void solve() {
	cout<<sz(ans)<<ln;
	each(x, ans) cout<<x<<ln;
	exit(0);
}

inline void go(vpi rec) {
	// cout<<"New instance of GO"<<ln;
	// each(x, rec) cout<<x.ff<<", "<<x.ss<<ln;
	// nwln
	time(&xd2);
	if(difftime(xd2, xd1) > 0.999) solve();

	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()
{
	time(&xd1);

	fastio
	cin>>K;

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

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

	solve();

	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!
*/

Compilation message

staciakampis.cpp:3: warning: ignoring '#pragma inline_recursion ' [-Wunknown-pragmas]
    3 | #pragma inline_recursion(on)
      |

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 29 ms 212 KB Output is correct
4 Correct 166 ms 292 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Incorrect 90 ms 292 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 826 ms 292 KB Output is correct
2 Correct 155 ms 304 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Runtime error 109 ms 262144 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 29 ms 212 KB Output is correct
4 Correct 166 ms 292 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Incorrect 90 ms 292 KB Output isn't correct
7 Halted 0 ms 0 KB -