Submission #110671

#	Time	Username	Problem	Language	Result	Execution time	Memory
110671		Breno_XD	Bitaro the Brave (JOI19_ho_t1)	C++14	20 / 100	1093 ms	239660 KiB

joi2019_ho_t1

#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define int long long

typedef pair<int,int> pii;

const int MAXN = 10000010;
int N,M, ans;
pii J[MAXN], O[MAXN], I[MAXN];
int oeJ[MAXN], oeO[MAXN], oeI[MAXN];
int contj, conto, conti;
char letra;

main(){

    //Inicializo com -1, indicando que não tem como chegar lá
    memset(oeJ, -1, sizeof(oeJ));
    memset(oeO, -1, sizeof(oeO));
    memset(oeI, -1, sizeof(oeI));

    //leitura
    scanf("%lld%lld", &N, &M);
    for(int i=1; i<=N; i++){
        for(int j=1; j<=M; j++){
            cin >> letra;
            if(letra == 'J'){
                J[++contj] = {i,j};
                //if(oeJ[i]==-1) oeJ[i] = contj;
            }
            if(letra == 'O'){
                O[++conto] = {i,j};
                if(oeO[i]==-1) oeO[i] = conto;
            }
            if(letra == 'I'){
                I[++conti] = {j,i};
                //if(oeI[i]==-1) oeI[i] = conti;
            }
        }
    }

    //contj--; conto--; conti--; // Agora guardam a posição final

    //Ordeno o vetor I
    sort(I+1, I+conti+1); //Ordena em ordem crescente

    for(int top=1; top<=MAXN; top++){
        //cout << endl;
        //cout << "Top: " << top << endl;
        int i = I[top].x;
        //cout << "i: " << i << "    oeI[i] = " << oeI[i] << endl;
        if(oeI[i]==-1) oeI[i] = top;
        //cout << "oeI[i] = " << oeI[i] << endl;
    }

    /*
    cout << "Vetor J: " << endl;
    for(int i=1; i<=contj; i++) cout << J[i].x << " " << J[i].y << endl;
    cout << endl;

    cout << "Vetor O: " << endl;
    for(int i=1; i<=conto; i++) cout << O[i].x << " " << O[i].y << endl;
    cout << endl;

    cout << "Vetor I: " << endl;
    for(int i=1; i<=conti; i++) cout << I[i].x << " " << I[i].y << endl;
    cout << endl;

    cout << "oeJ: ";
    for(int i=1; i<=10; i++) cout << oeJ[i] << " ";
    cout << endl;

    cout << "oeO: ";
    for(int i=1; i<=10; i++) cout << oeO[i] << " ";
    cout << endl;

    cout << "oeI: ";
    for(int i=1; i<=10; i++) cout << oeI[i] << " ";
    cout << endl;
    cout << endl;
    */

    for(int ind=1; ind<=contj; ind++){ //Indice que percorre J

        int i = J[ind].x; int j = J[ind].y;

        for(int ini = oeO[i]; O[ini].x==i; ini++){

            int l = O[ini].y;

            if(j<l){ //Se for um valor possível, continuo a buscar

                for(int comeco = oeI[j]; I[comeco].x==j; comeco++){
                    int k = I[comeco].y;

                    if(i<k){
                        ans++;
                        //cout << "Encontrei: (i,j,k,l) = (" << i << ", " << j << ", " << k << ", " << l << ")" << endl;
                    }
                }

            }
            //Caso contrário eu dessprezo, pois não é uma possibilidade
        }

    }

    cout << ans << endl;
    return 0;
}

Compilation message (stderr)

joi2019_ho_t1.cpp:16:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
joi2019_ho_t1.cpp: In function 'int main()':
joi2019_ho_t1.cpp:24:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld%lld", &N, &M);
     ~~~~~^~~~~~~~~~~~~~~~~~~~
joi2019_ho_t1.cpp:51:13: warning: iteration 10000009 invokes undefined behavior [-Waggressive-loop-optimizations]
         int i = I[top].x;
             ^
joi2019_ho_t1.cpp:48:23: note: within this loop
     for(int top=1; top<=MAXN; top++){
                    ~~~^~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 0 / 30
• Subtask 3: 0 / 50