oj.uz

Submission #820181

# Submission time Handle Problem Language Result Execution time Memory
820181 2023-08-11T00:04:05 Z gg123_pe Cutting a rectangle (LMIO18_staciakampis) C++14
45 / 100
 87 ms 3744 KB 
#include <bits/stdc++.h> 
using namespace std; 

typedef long long ll; 
#define f(i,a,b) for(int i = a; i < b; i++)
#define fa(i,a,b) for(int i = a; i >= b; i--)

const int N = 1e5 + 5, M = 5e6 + 5; 

int n; 
ll a[N], b[N], s[N]; 
bool l[N], r[N], ans[M];  
int p[11]; 

void print(){
    int res = 0; 
    f(i,1,M) res += ans[i]; 

    cout << res << "\n"; 
    f(i,1,M) if(ans[i]) cout << i << "\n"; 
}
ll sum(int l, int r){
    return s[r] - s[l-1]; 
}
int main(){
    cin >> n; 

    f(i,1,n+1) {
        cin >> a[i] >> b[i]; 
        s[i] = s[i-1] + a[i]; 
    }

    if(n <= 10){
        f(i,1,11) p[i] = i;  

        while(1){
            int x = a[p[1]], y = b[p[1]]; 
            bool flag = 1; 
            f(i,2,n+1){
                int u = a[p[i]], v = b[p[i]]; 
                if(u == x or v == x){
                    if(u == x) y += v; 
                    else y += u; 
                }
                else if(u == y or v == y){
                    if(u == y) x += v; 
                    else x += u; 
                }
                else{
                    flag = 0; 
                }
            }
            if(flag) 
                ans[min(x, y)] = 1; 

            if(next_permutation(p+1, p+n+1) == false) break; 
        }
        print(); 
        return 0; 
    }
    l[1] = r[n] = 1; 
    f(i,2,n+1) l[i] = (l[i-1]&(a[i-1] + 1 == a[i])); 
    fa(i,n-1,1) r[i] = (r[i+1]&(a[i] + 1 == a[i+1])); 

    ans[1] = 1; 

    // check b = 0
    ll curr = 0; 
    bool ra = 0; 
    f(i,1,n){
        curr += a[i]; 
        if(a[i] == 2) ra = 1;  
    }
    if(curr == a[n] or (ra and curr - 2 == a[n])) ans[2] = 1; 

    f(id,1,M-3){
        bool flag = 0; 
        if(n < 2*id + 3) break; 
        int ini = (a[1] == 1) ? 2 : 1; 
        if(a[ini] != 2) continue;
        // 1
        if(l[ini+id-1] and r[n-id] and ini+id-1 < n-id and s[n] - sum(ini, ini+id-1) - sum(n-id, n) == a[n-id])
            flag = 1; 
        // 2 
        if(l[ini+id] and r[n-id] and ini+id < n-id and s[n] - sum(ini, ini+id) - sum(n-id, n) == a[n-id])
            flag = 1;

        ans[id+2] = flag; 
    }

    print(); 

    return 0; 
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 332 KB Output is correct
2 Correct 5 ms 212 KB Output is correct
3 Correct 12 ms 304 KB Output is correct
4 Correct 87 ms 320 KB Output is correct
5 Correct 5 ms 340 KB Output is correct
6 Correct 60 ms 328 KB Output is correct
7 Correct 6 ms 308 KB Output is correct
8 Correct 75 ms 316 KB Output is correct
9 Correct 12 ms 328 KB Output is correct
10 Correct 5 ms 328 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 316 KB Output is correct
2 Correct 12 ms 328 KB Output is correct
3 Correct 5 ms 328 KB Output is correct
4 Correct 37 ms 2852 KB Output is correct
5 Correct 40 ms 2864 KB Output is correct
6 Correct 38 ms 2816 KB Output is correct
7 Correct 40 ms 2816 KB Output is correct

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 332 KB Output is correct
2 Correct 5 ms 212 KB Output is correct
3 Correct 12 ms 304 KB Output is correct
4 Correct 87 ms 320 KB Output is correct
5 Correct 5 ms 340 KB Output is correct
6 Correct 60 ms 328 KB Output is correct
7 Correct 6 ms 308 KB Output is correct
8 Correct 75 ms 316 KB Output is correct
9 Correct 12 ms 328 KB Output is correct
10 Correct 5 ms 328 KB Output is correct
11 Correct 37 ms 2852 KB Output is correct
12 Correct 40 ms 2864 KB Output is correct
13 Correct 38 ms 2816 KB Output is correct
14 Correct 40 ms 2816 KB Output is correct
15 Incorrect 40 ms 3744 KB Output isn't correct
16 Halted 0 ms 0 KB -