oj.uz

Submission #823681

# Submission time Handle Problem Language Result Execution time Memory
823681 2023-08-13T00:48:40 Z Fischer Cutting a rectangle (LMIO18_staciakampis) C++14
100 / 100
 75 ms 35160 KB 
#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.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 19924 KB Output is correct
2 Correct 7 ms 19924 KB Output is correct
3 Correct 30 ms 19876 KB Output is correct
4 Correct 46 ms 20556 KB Output is correct
5 Correct 8 ms 19896 KB Output is correct
6 Correct 47 ms 20412 KB Output is correct
7 Correct 8 ms 19924 KB Output is correct
8 Correct 8 ms 19924 KB Output is correct
9 Correct 8 ms 19924 KB Output is correct
10 Correct 9 ms 19924 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 19924 KB Output is correct
2 Correct 8 ms 19924 KB Output is correct
3 Correct 9 ms 19924 KB Output is correct
4 Correct 21 ms 22356 KB Output is correct
5 Correct 25 ms 22272 KB Output is correct
6 Correct 23 ms 22328 KB Output is correct
7 Correct 24 ms 22316 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 19924 KB Output is correct
2 Correct 7 ms 19924 KB Output is correct
3 Correct 30 ms 19876 KB Output is correct
4 Correct 46 ms 20556 KB Output is correct
5 Correct 8 ms 19896 KB Output is correct
6 Correct 47 ms 20412 KB Output is correct
7 Correct 8 ms 19924 KB Output is correct
8 Correct 8 ms 19924 KB Output is correct
9 Correct 8 ms 19924 KB Output is correct
10 Correct 9 ms 19924 KB Output is correct
11 Correct 21 ms 22356 KB Output is correct
12 Correct 25 ms 22272 KB Output is correct
13 Correct 23 ms 22328 KB Output is correct
14 Correct 24 ms 22316 KB Output is correct
15 Correct 67 ms 35160 KB Output is correct
16 Correct 44 ms 23068 KB Output is correct
17 Correct 60 ms 23812 KB Output is correct
18 Correct 23 ms 30548 KB Output is correct
19 Correct 37 ms 23388 KB Output is correct
20 Correct 61 ms 22388 KB Output is correct
21 Correct 8 ms 19868 KB Output is correct
22 Correct 75 ms 21500 KB Output is correct