Submission #820181

#	Time	Username	Problem	Language	Result	Execution time	Memory
820181		gg123_pe	Cutting a rectangle (LMIO18_staciakampis)	C++14	45 / 100	87 ms	3744 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];  
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 / 25
• Subtask 2: 20 / 20
• Subtask 3: 0 / 55