oj.uz

Submission #823673

# Submission time Handle Problem Language Result Execution time Memory
823673 2023-08-12T23:58:43 Z Fischer Cutting a rectangle (LMIO18_staciakampis) C++14
45 / 100
 1000 ms 140132 KB 
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#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];
vector<int> valid;
vector<int> ba[maxa];
int T;

long long get(long long x) {
    if (vis1[x] == T) return 0;
    vis1[x] = T;
    long long sum = 0;
    for (int id : ba[x]) {
        if (vis[id] < T) {
            vis[id] = T;
            sum += a[id][0];
        }
    }
    return sum;
}

bool check(long long l, long long r) {
    for (int i=0; i<n; ++i) {
        if (vis[i] == T) continue;
        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;
            if (suma[l] + a[i][0] + a[i+1][0] < r) 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 (vis[need_id] == T) return 0; 
                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) {
        if (i >= maxa) continue;
        if (area % i) continue;
        if (suma[i] + 2 * a[0][0] < 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;
        ba[a[i][1]].push_back(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 67 ms 137308 KB Output is correct
2 Correct 66 ms 137292 KB Output is correct
3 Correct 90 ms 137336 KB Output is correct
4 Correct 104 ms 137452 KB Output is correct
5 Correct 67 ms 137308 KB Output is correct
6 Correct 108 ms 137480 KB Output is correct
7 Correct 68 ms 137248 KB Output is correct
8 Correct 67 ms 137284 KB Output is correct
9 Correct 66 ms 137184 KB Output is correct
10 Correct 67 ms 137256 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 137284 KB Output is correct
2 Correct 66 ms 137184 KB Output is correct
3 Correct 67 ms 137256 KB Output is correct
4 Correct 80 ms 139112 KB Output is correct
5 Correct 85 ms 139192 KB Output is correct
6 Correct 81 ms 139084 KB Output is correct
7 Correct 84 ms 139184 KB Output is correct

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 137308 KB Output is correct
2 Correct 66 ms 137292 KB Output is correct
3 Correct 90 ms 137336 KB Output is correct
4 Correct 104 ms 137452 KB Output is correct
5 Correct 67 ms 137308 KB Output is correct
6 Correct 108 ms 137480 KB Output is correct
7 Correct 68 ms 137248 KB Output is correct
8 Correct 67 ms 137284 KB Output is correct
9 Correct 66 ms 137184 KB Output is correct
10 Correct 67 ms 137256 KB Output is correct
11 Correct 80 ms 139112 KB Output is correct
12 Correct 85 ms 139192 KB Output is correct
13 Correct 81 ms 139084 KB Output is correct
14 Correct 84 ms 139184 KB Output is correct
15 Correct 117 ms 140132 KB Output is correct
16 Correct 101 ms 139356 KB Output is correct
17 Correct 120 ms 139556 KB Output is correct
18 Correct 84 ms 139084 KB Output is correct
19 Correct 96 ms 139420 KB Output is correct
20 Correct 119 ms 139124 KB Output is correct
21 Correct 68 ms 137384 KB Output is correct
22 Execution timed out 1088 ms 139008 KB Time limit exceeded
23 Halted 0 ms 0 KB -