oj.uz

Submission #110671

# Submission time Handle Problem Language Result Execution time Memory
110671 2019-05-11T20:13:48 Z Breno_XD Bitaro the Brave (JOI19_ho_t1) C++14
20 / 100
 1000 ms 239660 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 223 ms 235572 KB Output is correct
2 Correct 225 ms 235488 KB Output is correct
3 Correct 219 ms 235480 KB Output is correct
4 Correct 219 ms 235496 KB Output is correct
5 Correct 220 ms 235688 KB Output is correct
6 Correct 224 ms 235688 KB Output is correct
7 Correct 224 ms 235728 KB Output is correct
8 Correct 221 ms 235568 KB Output is correct
9 Correct 225 ms 235640 KB Output is correct
10 Correct 222 ms 235640 KB Output is correct
11 Correct 221 ms 235604 KB Output is correct
12 Correct 249 ms 235640 KB Output is correct
13 Correct 233 ms 235640 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 223 ms 235572 KB Output is correct
2 Correct 225 ms 235488 KB Output is correct
3 Correct 219 ms 235480 KB Output is correct
4 Correct 219 ms 235496 KB Output is correct
5 Correct 220 ms 235688 KB Output is correct
6 Correct 224 ms 235688 KB Output is correct
7 Correct 224 ms 235728 KB Output is correct
8 Correct 221 ms 235568 KB Output is correct
9 Correct 225 ms 235640 KB Output is correct
10 Correct 222 ms 235640 KB Output is correct
11 Correct 221 ms 235604 KB Output is correct
12 Correct 249 ms 235640 KB Output is correct
13 Correct 233 ms 235640 KB Output is correct
14 Correct 810 ms 238760 KB Output is correct
15 Correct 223 ms 235512 KB Output is correct
16 Correct 275 ms 237560 KB Output is correct
17 Correct 238 ms 235632 KB Output is correct
18 Execution timed out 1093 ms 239660 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 223 ms 235572 KB Output is correct
2 Correct 225 ms 235488 KB Output is correct
3 Correct 219 ms 235480 KB Output is correct
4 Correct 219 ms 235496 KB Output is correct
5 Correct 220 ms 235688 KB Output is correct
6 Correct 224 ms 235688 KB Output is correct
7 Correct 224 ms 235728 KB Output is correct
8 Correct 221 ms 235568 KB Output is correct
9 Correct 225 ms 235640 KB Output is correct
10 Correct 222 ms 235640 KB Output is correct
11 Correct 221 ms 235604 KB Output is correct
12 Correct 249 ms 235640 KB Output is correct
13 Correct 233 ms 235640 KB Output is correct
14 Correct 810 ms 238760 KB Output is correct
15 Correct 223 ms 235512 KB Output is correct
16 Correct 275 ms 237560 KB Output is correct
17 Correct 238 ms 235632 KB Output is correct
18 Execution timed out 1093 ms 239660 KB Time limit exceeded
19 Halted 0 ms 0 KB -