oj.uz

답안 #820180

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
820180 2023-08-10T23:49:58 Z gg123_pe Cutting a rectangle (LMIO18_staciakampis) C++14
20 / 100
 42 ms 3740 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];  

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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 340 KB Output is correct
2 Correct 7 ms 340 KB Output is correct
3 Correct 5 ms 340 KB Output is correct
4 Correct 36 ms 3584 KB Output is correct
5 Correct 38 ms 3740 KB Output is correct
6 Correct 42 ms 3680 KB Output is correct
7 Correct 38 ms 3648 KB Output is correct

Subtask #3
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -