Submission #820180

#	Time	Username	Problem	Language	Result	Execution time	Memory
820180		gg123_pe	Cutting a rectangle (LMIO18_staciakampis)	C++14	20 / 100	42 ms	3740 KiB

staciakampis

#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];  

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]; 
    }

    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: 0 / 25
• Subtask 2: 20 / 20
• Subtask 3: 0 / 55