Submission #1233659

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233659		msrivera1404	Mosaic (IOI24_mosaic)	C++20	8 / 100	76 ms	11336 KiB

mosaic

#include "mosaic.h"
#include <iostream>
#include <numeric>
#include <vector>
#include <algorithm>


std::vector<long long> mosaic(std::vector<int> X, std::vector<int> Y,
                              std::vector<int> T, std::vector<int> B,
                              std::vector<int> L, std::vector<int> R) {

    int Q = (int)T.size();
    int N = (int)X.size();

    
    
    //RESUELVE SUBTAREA 1 Y 2
    // std::vector <std::vector <int>> mosaico(N, std::vector<int>(N));
    // for(int j=0; j<N;++j){
    //     mosaico[0][j]=X[j];
    // }
    // for(int i=0;i<N;++i){
    //     mosaico[i][0]=Y[i];
    // }

    // for(int i=1; i<N; ++i){
    //     for(int j=1;j<N;++j){
    //         if(mosaico[i-1][j]==0 && mosaico[i][j-1]==0){
    //             mosaico[i][j]=1;
    //         }
    //         else{
    //             mosaico[i][j]=0;
    //         }
    //     }
    // }
    // std::vector <long long> respuestas(Q); 
    // for(int k=0; k<Q; ++k){
    //     long long current_blacks=0; 
    //     int r1=T[k]; 
    //     int r2=B[k]; 
    //     int c1=L[k]; 
    //     int c2=R[k];

    //     for(int i=r1; i<=r2; ++i){
    //         for(int j=c1; j<=c2; ++j){
    //             if(mosaico[i][j]==1){
    //                 current_blacks++;
    //             }
    //         }
    //     }
    //     respuestas[k]=current_blacks;
    // }
    // return respuestas;

    //RESUELVE SUBTAREA 3
    // std::vector <long long> respuestas(Q);                             
    // std::vector <long long> prefix_sums(N+1,0);
    // std::partial_sum(X.begin(), X.end(), prefix_sums.begin()+1); 

    // for(int k=0; k<Q; ++k){
    //     long long current_blacks=0; 
    //     int r1=T[k]; 
        
    //     int c1=L[k]; 
    //     int c2=R[k];

    //     current_blacks=prefix_sums[c2+1]-prefix_sums[c1];
    //     respuestas[k]=current_blacks;
    // }

    // return respuestas;

    // //RESUELVE SUBTAREA 1,2,4
    // std::vector <std::vector <int>> mosaico(N, std::vector<int>(N));
    // for(int j=0; j<N;++j){
    //     mosaico[0][j]=X[j];
    // }
    // for(int i=0;i<N;++i){
    //     mosaico[i][0]=Y[i];
    // }

    // for(int i=1; i<N; ++i){
    //     for(int j=1;j<N;++j){
    //         if(mosaico[i-1][j]==0 && mosaico[i][j-1]==0){
    //             mosaico[i][j]=1;
    //         }
    //         else{
    //             mosaico[i][j]=0;
    //         }
    //     }
    // }
    // std::vector <long long> respuestas(Q); 

    // std::vector<std::vector<long long>> pref_sum_2D(N+1, std::vector <long long> (N+1,0));

    // for(int i=0; i<N; ++i){
    //     std::partial_sum(mosaico[i].begin(), mosaico[i].end(), pref_sum_2D[i+1].begin()+1);
    // }
    // for(int j=1; j<=N; ++j){
    //    for(int i=1; i<=N;++i){
    //     pref_sum_2D[i][j]+=pref_sum_2D[i-1][j];
    //    }
    // }

    // for(int k=0; k<Q;++k){
    //     int r1=T[k]; int r2=B[k]; 
    //     int c1=L[k]; int c2=R[k]; 

    //     long long current_blacks=pref_sum_2D[r2+1][c2+1]-pref_sum_2D[r1][c2+1]-pref_sum_2D[r2+1][c1]+pref_sum_2D[r1][c1];
    //     respuestas[k]=current_blacks;
    // }
    // return respuestas;


    //RESUELVE SUBTAREA 5
    std::vector <long long> respuestas (Q); 

    for(int k=0; k<Q;++k){
        int r1=T[k]; int r2=B[k]; 
        int c1=L[k]; int c2=R[k]; 

        long long current_blacks=0;

        int effective_r1=std::max(r1,1); 
        int effective_c1=std::max(c1,1); 

        long long checkboard_rows=std::max(0,r2-effective_r1+1); 
        long long checkboard_cols=std::max(0,c2-effective_c1+1); 
        long long checkboard_area=checkboard_rows*checkboard_cols; 

        current_blacks=checkboard_area/2; 

        if(checkboard_area%2!=0){
            if((effective_r1+effective_c1)%2==0){
                current_blacks++;
            }
        }
        respuestas[k]=current_blacks;
    }
    return respuestas;

}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 7
• Subtask 4: 0 / 10
• Subtask 5: 8 / 8
• Subtask 6: 0 / 22
• Subtask 7: 0 / 19
• Subtask 8: 0 / 22