Submission #823681

#	Time	Username	Problem	Language	Result	Execution time	Memory
823681		Fischer	Cutting a rectangle (LMIO18_staciakampis)	C++14	100 / 100	75 ms	35160 KiB

staciakampis

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

const int maxn = 1e5 + 10;
const int maxa = 5e6 + 1;
int a[maxn][2];
int d[maxa];
int vis[maxn];
int vis1[maxa];
int n;
long long suma[maxa];
int vis2[maxa];
long long minu[maxa];
vector<int> valid;
int T;

void del_box(int i) {
    if (vis2[a[i][1]] < T) {
        vis2[a[i][1]] = T;
        minu[a[i][1]] = a[i][0];
    } else {
        minu[a[i][1]] += a[i][0];
    }
}

bool verify(int i) {
    if (vis[i] == T) return 0;
    if (vis1[a[i][1]] == T) return 0;
    return 1;
}


long long get(int x) {
    if (vis1[x] == T) return 0;
    vis1[x] = T;
    if (vis2[x] < T) {
        vis2[x] = T; 
        minu[x] = 0;
    }
    return suma[x] - minu[x]; 
}

bool check(long long l, long long r) {
    for (int i=0; i<n; ++i) {
        if (!verify(i)) continue;
        del_box(i);
        vis[i] = T;
        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 {
            if (l < a[i][1] || r < a[i][0]) return 0;
            long long er = r - a[i][0];    
            if (l >= maxa) return 0;
            long long len = get(l); 
            if (len > er) return 0;
            if (len < er) {
                if (l < er - len) return 0;
                int need_id = d[l];
                if (need_id == -1) return 0;
                if (a[need_id][1] != er - len) return 0;
                if (!verify(need_id)) return 0; 
                del_box(need_id);
                vis[need_id] = T;
            }
            l -= a[i][1];
            r = a[i][0];
        }   
    }   
    if (r < 0 || l < 0) return 0;
    return l == 0 || r == 0;
}

void solve(long long area) {
    for (int i = 1; i*1ll*i <= area && i < maxa; ++i) {
        if (area % i) continue;
        T++;
        if (check(i, area / i)) {
            valid.push_back(i);
        }
    }   
}   

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;
        suma[a[i][1]] += a[i][0];
        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: 25 / 25
• Subtask 2: 20 / 20
• Subtask 3: 55 / 55