oj.uz

Submission #823651

# Submission time Handle Problem Language Result Execution time Memory
823651 2023-08-12T23:44:30 Z Fischer Cutting a rectangle (LMIO18_staciakampis) C++14
45 / 100
 1000 ms 140220 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];
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 el = l;
            long long er = r - a[i][0];    
            if (l >= maxa) return 0;
            if (suma[l] + 2 * a[i][0] < r) return 0;
            long long len = get(l); 
            if (len > er) return 0;
            if (len < er) {
                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 (area % i) continue;
        if (i >= maxa) 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;
}

Compilation message

staciakampis.cpp: In function 'bool check(long long int, long long int)':
staciakampis.cpp:43:23: warning: unused variable 'el' [-Wunused-variable]
   43 |             long long el = l;
      |                       ^~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 137292 KB Output is correct
2 Correct 60 ms 137224 KB Output is correct
3 Correct 81 ms 137256 KB Output is correct
4 Correct 99 ms 137600 KB Output is correct
5 Correct 60 ms 137204 KB Output is correct
6 Correct 102 ms 137624 KB Output is correct
7 Correct 62 ms 137192 KB Output is correct
8 Correct 61 ms 137312 KB Output is correct
9 Correct 60 ms 137192 KB Output is correct
10 Correct 60 ms 137216 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 137312 KB Output is correct
2 Correct 60 ms 137192 KB Output is correct
3 Correct 60 ms 137216 KB Output is correct
4 Correct 72 ms 139108 KB Output is correct
5 Correct 81 ms 139456 KB Output is correct
6 Correct 75 ms 139156 KB Output is correct
7 Correct 77 ms 139072 KB Output is correct

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 137292 KB Output is correct
2 Correct 60 ms 137224 KB Output is correct
3 Correct 81 ms 137256 KB Output is correct
4 Correct 99 ms 137600 KB Output is correct
5 Correct 60 ms 137204 KB Output is correct
6 Correct 102 ms 137624 KB Output is correct
7 Correct 62 ms 137192 KB Output is correct
8 Correct 61 ms 137312 KB Output is correct
9 Correct 60 ms 137192 KB Output is correct
10 Correct 60 ms 137216 KB Output is correct
11 Correct 72 ms 139108 KB Output is correct
12 Correct 81 ms 139456 KB Output is correct
13 Correct 75 ms 139156 KB Output is correct
14 Correct 77 ms 139072 KB Output is correct
15 Correct 112 ms 140220 KB Output is correct
16 Correct 101 ms 139344 KB Output is correct
17 Correct 113 ms 139736 KB Output is correct
18 Correct 73 ms 139080 KB Output is correct
19 Correct 89 ms 139448 KB Output is correct
20 Correct 115 ms 139208 KB Output is correct
21 Correct 62 ms 137384 KB Output is correct
22 Execution timed out 1088 ms 138972 KB Time limit exceeded
23 Halted 0 ms 0 KB -