Submission #1234113

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234113		ThommyDB	Cutting a Rectangle (BOI24_rectangle)	C++20	100 / 100	179 ms	241680 KiB

Main

#include<bits/stdc++.h>

using namespace std;
#define int long long

signed main(){
    int k;
    cin >> k;
    vector<pair<int, int>> len(k);
    int area = 0;
    int mxl=0;
    for(int i = 0; i < k; i++){
        cin >> len[i].first >> len[i].second;
        area += len[i].first*len[i].second;
        mxl = max(mxl, len[i].second);
    }
    vector<vector<int>> lng(len.back().first+1);
    vector<vector<int>> shrt(len.back().first+1);
    for(int i = 0; i < k; i++){
        lng[len[i].first].push_back(i);
        shrt[len[i].second].push_back(i);
    }
    vector<int> ans;
    for(int i = 1; i < len.back().first+1; i++){
        if(!(area%i==0 && i <= area/i)){
            continue;
        }
        int a = i;
        int b = area/i;
        vector<bool> visited(len.back().first+1, false);
        while(true){
            bool done = false;
            if(a < b) swap(a, b);
            if(a <= len.back().first){
                for(auto u : lng[a]){
				    if(!visited[u]){
					    visited[u] = true;
					    done = true;
					    b -= len[u].second;
				    }
			    }
            }
            
            if(done)continue;
            for(auto u : shrt[b]){
				if(!visited[u]){
					visited[u] = true;
					done = true;
					a -= len[u].first;
				}
			}

			if(done)continue;
			for(auto u : lng[b]){
				if(!visited[u]){
					visited[u] = true;
					done = true;
					a -= len[u].second;
				}
			}

			if(!done)break;
        }
        if(a * b == 0)ans.push_back(i);
    }
    cout << ans.size() << "\n";
    for(auto u : ans){
        cout << u << "\n";
    }
}

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