Submission #823031

#	Time	Username	Problem	Language	Result	Execution time	Memory
823031		Fischer	Cutting a rectangle (LMIO18_staciakampis)	C++14	0 / 100	48 ms	79700 KiB

staciakampis

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 10;
const int maxa = 1e7 + 1;
int a[maxn][2];
int d[maxa];
int vis[maxn];
int n;
vector<int> valid;

bool check(int t, int l, int r) {
    for (int i=0; i<n; ++i) {
        if (vis[i] == t) continue;
        if (r < l) swap(l, r);
        if (l < 0) return 0; 
        if (a[i][0] == r) {
            l -= a[i][1];
        } else if (a[i][0] == l) {
            r -= a[i][1];
        } else if (a[i][1] == l) {
            r -= a[i][0];
        } else {
            int el = l;
            int er = r - a[i][0];
            if (er < el) swap(el, er);
            if (el < 0) return 0;
            if (d[er] == -1) return 0;
            if (vis[d[er]] == t) return 0;
            vis[d[er]] = t;
            l -= a[i][1];
            r = a[i][0];
        }   
    }   
    return l == 0 || r == 0;
}

const long long maxA = 5e13;
void solve(long long area) {
    if (area >= maxA) return;
    int T = 0;
    for (int i = 1; i*1ll*i <= area; ++i) {
        if (area % i) continue;
        if (area / i >= 2 * maxa) continue;
        T++;
        if (check(T, i, area / i)) {
            valid.push_back(i);
        }
    }   
    return;
}   

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin>>n;
    long long area = 0;
    memset(d, -1, sizeof d);
    for (int i=0; i<n; ++i) {
        cin>>a[n-i-1][0]>>a[n-i-1][1];
    }  
    d[0] = n;
    for (int i=0; i<n; ++i) {
        d[a[i][0]] = i;
        area += a[i][0]*1ll*a[i][1];
    }
    solve(area);
    cout << valid.size() << '\n';
    for (auto e : valid) {
        cout << e << '\n';
    }
    return 0;
}

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