oj.uz

Submission #823646

# Submission time Handle Problem Language Result Execution time Memory
823646 2023-08-12T23:35:00 Z Fischer Cutting a rectangle (LMIO18_staciakampis) C++14
45 / 100
 1000 ms 143164 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;
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;
            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;
        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);
        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:42:23: warning: unused variable 'el' [-Wunused-variable]
   42 |             long long el = l;
      |                       ^~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 137292 KB Output is correct
2 Correct 62 ms 137292 KB Output is correct
3 Correct 83 ms 137280 KB Output is correct
4 Correct 103 ms 137504 KB Output is correct
5 Correct 64 ms 137292 KB Output is correct
6 Correct 100 ms 137308 KB Output is correct
7 Correct 62 ms 137304 KB Output is correct
8 Correct 62 ms 137272 KB Output is correct
9 Correct 63 ms 137276 KB Output is correct
10 Correct 64 ms 137292 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 137272 KB Output is correct
2 Correct 63 ms 137276 KB Output is correct
3 Correct 64 ms 137292 KB Output is correct
4 Correct 75 ms 139192 KB Output is correct
5 Correct 77 ms 139116 KB Output is correct
6 Correct 77 ms 139132 KB Output is correct
7 Correct 81 ms 139084 KB Output is correct

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 137292 KB Output is correct
2 Correct 62 ms 137292 KB Output is correct
3 Correct 83 ms 137280 KB Output is correct
4 Correct 103 ms 137504 KB Output is correct
5 Correct 64 ms 137292 KB Output is correct
6 Correct 100 ms 137308 KB Output is correct
7 Correct 62 ms 137304 KB Output is correct
8 Correct 62 ms 137272 KB Output is correct
9 Correct 63 ms 137276 KB Output is correct
10 Correct 64 ms 137292 KB Output is correct
11 Correct 75 ms 139192 KB Output is correct
12 Correct 77 ms 139116 KB Output is correct
13 Correct 77 ms 139132 KB Output is correct
14 Correct 81 ms 139084 KB Output is correct
15 Correct 114 ms 143164 KB Output is correct
16 Correct 96 ms 139388 KB Output is correct
17 Correct 111 ms 139520 KB Output is correct
18 Correct 74 ms 140628 KB Output is correct
19 Correct 90 ms 139340 KB Output is correct
20 Correct 118 ms 139468 KB Output is correct
21 Correct 61 ms 137328 KB Output is correct
22 Execution timed out 1082 ms 138932 KB Time limit exceeded
23 Halted 0 ms 0 KB -