Submission #1265973

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265973		herominhsteve	Cutting a Rectangle (BOI24_rectangle)	C++20	0 / 100	52 ms	12736 KiB

Main

#include <bits/stdc++.h>
#define el '\n'
#define FNAME "rectangle"
#define allof(x) x.begin(),x.end()
#define allof1(x) x.begin()+1,x.end()
#define mset(x,n) memset(x,(n),sizeof(x))
using namespace std;
const long long MOD = (long long) 1e9+7;
template<class X,class Y> bool minimize(X &a,Y b){ if (a>b) {a=b; return true;} return false;}
template<class X,class Y> bool maximize(X &a,Y b){ if (a<b) {a=b; return true;} return false;}

void setup(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
	if (fopen(FNAME".inp","r")){
		freopen(FNAME".inp","r",stdin);
		freopen(FNAME".out","w",stdout);
	}
}

int n;
vector<int> W,H; // ! assume W >= H
map<int,vector<int>> len;
long long area;

void init(){
	cin>>n;
	W.resize(n);
	H.resize(n);
	for (int i=0;i<n;i++){
		cin>>W[i]>>H[i];
		len[W[i]].push_back(i);
		len[H[i]].push_back(i);
		area += W[i] * H[i];
	}
}

void sol(){
	vector<bool> visited(n,0);
	int ptr=n-1;
	int cnt=0;
	int w,h;
	
	function<void(int)> cut = [&] (int ID) -> void {
		visited[ID] = 1;
		cnt++;
		if (w<h) swap(w,h);
		if (ID < ptr) return;
		while (ptr>=0 and visited[ptr]) ptr--;
	};

	set<int> res;

	for (pair<int,vector<int>> p : len){
		int curH = p.first;
		if (area % curH) continue;
		int curZ = min(area/curH, 1ll* curH);
		h = curH;
		w = area/curH;
		if (w<h) swap(w,h);

		fill(allof(visited),0);
		cnt=0;
		ptr = n-1;
		bool check=1;
		while (cnt<n and check){
			check=0;
			if (ptr>=0){
				if (W[ptr] > w) break;
				if (W[ptr] == w){
					h -= H[ptr];
					check=1;
					cut(ptr);
					continue;
				}
			}
			if (len.count(h)){
				for (int x : len[h]){
					if (visited[x] or H[x]!=h) continue;
					check=1;
					w -= W[x];
					cut(x);
				}
				if (check) continue;
				int x = len[h].front();
				if (visited[x] or W[x] != h) continue;
				w -= H[x];
				check=1;
				cut(x);
			}
			if (!check) break;
		}
		if (cnt==n) res.insert(curZ);
	}
	cout<<res.size()<<el;
	for (int x : res) cout<<x<<el;
}

int main(){
    setup();
    init();
    sol();
}

Compilation message (stderr)

Main.cpp: In function 'void setup()':
Main.cpp:16:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |                 freopen(FNAME".inp","r",stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:17:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |                 freopen(FNAME".out","w",stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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