제출 #1316143

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1316143		antarbanik	Pyramids (IOI24_pyramids)	C++20	0 / 100	1093 ms	4348 KiB

pyramids

#include<bits/stdc++.h>
using namespace std;

/*

N pyramids

i-th pyramid -> a[i] stones


everyday,
same length er A & B array er ekta subarr choose korbo


jana lagbo if it's possible to transform A[l-r] -> B[x-y]



transformation rules:







*/

vector<int> a, b;

void init(vector<int> A, vector<int> B) {
    a = A;
    b = B;
}



bool can_transform(int l, int r, int x, int y){
    int n = a.size();
    vector<int> prefA(n+1), prefB(n+1);
    prefA[0] = a[0];
    prefB[0] = b[0];

    for(int i = 1;i<n;++i){
        prefA[i] = prefA[i-1] + a[i];
        prefB[i] = prefB[i-1] + b[i];
    }


    // for(int i = 0;i<n;++i){
    //     cout<<prefA[i]<<" ";
    // }
    // cout<<endl<<endl;




    int tot = r - l + 1;

    map<int,int> s1;


    for(int i = 0;i<=n-tot;++i){

        // cout<<tot+i-1<<" "<<i<<endl;
        int minus = 0;
        if(i > 0){
            minus = prefA[i-1];
        }   

        int s = prefA[tot+i-1] - minus;
        s1[s] = 1;
    }       

    // cout<<endl;

    // for(auto e : s1){
    //     cout<<e.first<<" ";
    // }

    // cout<<endl;

    for(int i = 0;i<=n-tot;++i){

        int minus = 0;
        if(i > 0){
            minus = prefB[i-1];
        }   

        int s = prefB[tot+i-1] - minus;


        if(s1.count(s)){
            return 1;
        }



    }



    return 0;
}


// int32_t main(){

//     init({1, 20, 3, 40, 5}, {2, 2, 2, 4, 5});

//     cout<<can_transform(0, 2, 0, 2);


//     return 0;
// }

• Subtask 0: 0 / 0
• Subtask 1: 0 / 10
• Subtask 2: 0 / 40
• Subtask 3: 0 / 20
• Subtask 4: 0 / 30