Submission #908872

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
908872	2024-01-17T00:58:57 Z	vjudge1	Secret (JOI14_secret)	C++17	0 / 100	374 ms	4832 KB

secret

#include <vector>
#include <algorithm>
using namespace std;//

#include "secret.h"

int tree[4005];

struct estado{
  int pos;
  int ini;
  int fin;
};

int tam;

void Init(int N, int A[]){
    tam=N;
    for(int c=1; c <=4*N+1; c++){
        tree[c]=-1;
    }
    int ini=1;
    int fin=N+1;
    int pos=1;
    vector <estado> cola;
    while(1){
        if(fin-ini==2){
            tree[pos]=Secret(A[ini], A[fin-1]);
            tree[pos*2]=A[ini];
            tree[pos*2+1]=A[ini+1];
            pos=cola.back().pos;
            ini=cola.back().ini;
            fin=cola.back().fin;
            cola.pop_back();
            continue;
        }
        if(fin-ini==1){
            tree[pos]=A[ini];
            pos=cola.back().pos;
            ini=cola.back().ini;
            fin=cola.back().fin;
            cola.pop_back();
            continue;
        }
        if(ini == fin){
            pos=cola.back().pos;
            ini=cola.back().ini;
            fin=cola.back().fin;
            cola.pop_back();
            continue;
        }
        if(tree[pos*2]==-1){
            estado nuevo;
            nuevo.pos=pos;
            nuevo.ini=ini;
            nuevo.fin=fin;
            cola.push_back(nuevo);
            pos*=2;
            fin=(ini+fin)/2;
            continue;
        }
        if(tree[pos*2+1]==-1){
            estado nuevo;
            nuevo.pos=pos;
            nuevo.ini=ini;
            nuevo.fin=fin;
            cola.push_back(nuevo);
            pos*=2;
            pos++;
            ini=(ini+fin)/2;
            continue;
        }
        tree[pos]=Secret(tree[pos*2], tree[pos*2+1]);
        if(pos == 1)
            break;
        pos=cola.back().pos;
        ini=cola.back().ini;
        fin=cola.back().fin;
        cola.pop_back();
        continue;
    }
    /*for(int c=1; c <=4*N+1; c++){
        cout << tree[c] << " ";
    }*/
}
    
int Query(int L, int R){
    L++;
    R++;
    vector <int> op;
    int vis[40005];
    for(int c=1; c <=40002; c++){
        vis[c]=-1;
    }
    int ini=1;
    int fin=tam+1;
    int pos=1;
    vector <estado> cola;
    while(1){
        vis[pos]++;
        if(ini > R || fin <= L){
            pos=cola.back().pos;
            ini=cola.back().ini;
            fin=cola.back().fin;
            cola.pop_back();
            continue;
        }
        if(L <= ini && R >= fin-1){
            op.push_back(pos);
            pos=cola.back().pos;
            ini=cola.back().ini;
            fin=cola.back().fin;
            cola.pop_back();
            continue;
        }
        if(vis[pos*2]==-1){
            estado nuevo;
            nuevo.pos=pos;
            nuevo.ini=ini;
            nuevo.fin=fin;
            cola.push_back(nuevo);
            pos*=2;
            fin=(ini+fin)/2;
            continue;
        }
        if(vis[pos*2+1]==-1){
            estado nuevo;
            nuevo.pos=pos;
            nuevo.ini=ini;
            nuevo.fin=fin;
            cola.push_back(nuevo);
            pos*=2;
            pos++;
            ini=(ini+fin)/2;
            continue;
        }
        if(pos==1)
            break;
        pos=cola.back().pos;
        ini=cola.back().ini;
        fin=cola.back().fin;
        cola.pop_back();
    }
    sort(op.begin(), op.end());
    int resp=tree[op.back()];
    op.pop_back();
    while(!op.empty()){
        resp=Secret(resp, tree[op.back()]);
        op.pop_back();
    }
    return resp;
}

Subtask #1

0.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	97 ms	3600 KB	Wrong Answer: Query(222, 254) - expected : 34031541, actual : 307655478.
2	Incorrect	96 ms	3668 KB	Wrong Answer: Query(60, 375) - expected : 669221184, actual : 843233288.
3	Incorrect	96 ms	3664 KB	Wrong Answer: Query(211, 401) - expected : 674373968, actual : 213119272.
4	Incorrect	365 ms	4320 KB	Wrong Answer: Query(90, 497) - expected : 397934825, actual : 836796525.
5	Incorrect	364 ms	4324 KB	Wrong Answer: Query(587, 915) - expected : 752404486, actual : 799693888.
6	Incorrect	359 ms	4560 KB	Wrong Answer: Query(915, 915) - expected : 282904741, actual : 206870645.
7	Incorrect	366 ms	4832 KB	Wrong Answer: Query(84, 976) - expected : 742463504, actual : 613594163.
8	Incorrect	363 ms	4436 KB	Wrong Answer: Query(58, 987) - expected : 20022464, actual : 202667392.
9	Incorrect	374 ms	4328 KB	Wrong Answer: Query(33, 967) - expected : 676869696, actual : 30936558.
10	Incorrect	361 ms	4320 KB	Wrong Answer: Query(116, 961) - expected : 68487362, actual : 1084228.