oj.uz

답안 #823062

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
823062 2023-08-12T07:30:18 Z Fischer Cutting a rectangle (LMIO18_staciakampis) C++14
0 / 100
 52 ms 39444 KB 
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 10;
const int maxa = 5e6 + 1;
int a[maxn][2];
int d[2 * maxa];
int vis[maxn];
int n;
vector<int> valid;

bool check(int t, int l, int r) {
    for (int i=0; i<n; ++i) {
        if (vis[i] == t) continue;
        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]) return 0;
            vis[i] = t;
            int el = l;
            int er = r - a[i][0];
            if (er < el) swap(el, er);
            if (el < 0) return 0;
            if (d[er] == -1) return 0;
            if (a[d[er]][1] != el) return 0;
            if (vis[d[er]] == t) return 0;
            vis[d[er]] = t;
            l -= a[i][1];
            r = a[i][0];
        }   
    }   
    return 1;
}

const long long maxA = 5e13;
void solve(long long area) {
    if (area >= maxA) return;
    int T = 0;
    for (int i = 1; i*1ll*i <= area; ++i) {
        if (area % i) continue;
        if (area / i >= 2 * maxa) continue;
        T++;
        if (check(T, i, area / i)) {
            valid.push_back(i);
        }
    }   
    return;
}   

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;
        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
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 39380 KB Output is correct
2 Correct 13 ms 39380 KB Output is correct
3 Correct 34 ms 39436 KB Output is correct
4 Correct 50 ms 39444 KB Output is correct
5 Correct 13 ms 39352 KB Output is correct
6 Correct 52 ms 39380 KB Output is correct
7 Correct 12 ms 39380 KB Output is correct
8 Correct 15 ms 39388 KB Output is correct
9 Incorrect 14 ms 39380 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 39388 KB Output is correct
2 Incorrect 14 ms 39380 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 39380 KB Output is correct
2 Correct 13 ms 39380 KB Output is correct
3 Correct 34 ms 39436 KB Output is correct
4 Correct 50 ms 39444 KB Output is correct
5 Correct 13 ms 39352 KB Output is correct
6 Correct 52 ms 39380 KB Output is correct
7 Correct 12 ms 39380 KB Output is correct
8 Correct 15 ms 39388 KB Output is correct
9 Incorrect 14 ms 39380 KB Output isn't correct
10 Halted 0 ms 0 KB -