oj.uz

Submission #1072715

# Submission time Handle Problem Language Result Execution time Memory
1072715 2024-08-24T03:20:24 Z SiliconSquared Minerals (JOI19_minerals) C++14
40 / 100
 1000 ms 1880 KB 
#include "minerals.h"

using namespace std;
#include <vector>
#include <iostream>

int query(int x){return Query(x+1);}

int n;
struct mineral{
    int a,b;
    mineral(){a=0;b=n;}
};
vector<mineral> v;
vector<int> l;
vector<int> r;

void f(int a,int b){
    // cerr<<a<<','<<b<<';';
    for (int i=a;i<b;i++){
        query(l[i]);
    }
    for (int i=0;i<n;i++){
        if (v[i].a<=a && v[i].b>=b){
            if (query(r[i])>(b-a)){
                v[i].a=b;
            }else{
                v[i].b=b;
            }
            query(r[i]);
        }
    }
    for (int i=a;i<b;i++){
        query(l[i]);
    }
}

void Solve(int N) {
    int a,b,c;
    n=N;
    b=0;
    for (int i=0;i<2*n;i++){
        a=query(i);
        if (a>b){
            l.push_back(i);
            b=a;
        }else{
            r.push_back(i);
        }
    }
    for (int i=0;i<2*n;i++){query(i);}
    v.resize(n,mineral());
    vector<pair<int,int>> w;
    w.push_back({0,N});
    while (!w.empty()){
        a=w[w.size()-1].first;
        b=w[w.size()-1].second;
        c=(a+b)/2;
        w.pop_back();
        if (a+1==b||a==b){continue;}
        f(a,c);
        w.push_back({a,c});
        w.push_back({c,b});
    }
    for (int i=0;i<n;i++){
        Answer(r[i]+1,l[v[i].a]+1);
    }
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 5 ms 528 KB Output is correct
3 Correct 19 ms 600 KB Output is correct
4 Correct 76 ms 856 KB Output is correct
5 Correct 318 ms 1104 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 2 ms 344 KB Output is correct
6 Correct 5 ms 528 KB Output is correct
7 Correct 19 ms 600 KB Output is correct
8 Correct 76 ms 856 KB Output is correct
9 Correct 318 ms 1104 KB Output is correct
10 Correct 2 ms 344 KB Output is correct
11 Correct 127 ms 884 KB Output is correct
12 Correct 249 ms 1076 KB Output is correct
13 Correct 165 ms 1112 KB Output is correct
14 Correct 202 ms 1020 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 2 ms 344 KB Output is correct
6 Correct 5 ms 528 KB Output is correct
7 Correct 19 ms 600 KB Output is correct
8 Correct 76 ms 856 KB Output is correct
9 Correct 318 ms 1104 KB Output is correct
10 Correct 2 ms 344 KB Output is correct
11 Correct 127 ms 884 KB Output is correct
12 Correct 249 ms 1076 KB Output is correct
13 Correct 165 ms 1112 KB Output is correct
14 Correct 202 ms 1020 KB Output is correct
15 Execution timed out 1282 ms 1880 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 2 ms 344 KB Output is correct
6 Correct 5 ms 528 KB Output is correct
7 Correct 19 ms 600 KB Output is correct
8 Correct 76 ms 856 KB Output is correct
9 Correct 318 ms 1104 KB Output is correct
10 Correct 2 ms 344 KB Output is correct
11 Correct 127 ms 884 KB Output is correct
12 Correct 249 ms 1076 KB Output is correct
13 Correct 165 ms 1112 KB Output is correct
14 Correct 202 ms 1020 KB Output is correct
15 Execution timed out 1282 ms 1880 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 2 ms 344 KB Output is correct
6 Correct 5 ms 528 KB Output is correct
7 Correct 19 ms 600 KB Output is correct
8 Correct 76 ms 856 KB Output is correct
9 Correct 318 ms 1104 KB Output is correct
10 Correct 2 ms 344 KB Output is correct
11 Correct 127 ms 884 KB Output is correct
12 Correct 249 ms 1076 KB Output is correct
13 Correct 165 ms 1112 KB Output is correct
14 Correct 202 ms 1020 KB Output is correct
15 Execution timed out 1282 ms 1880 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 2 ms 344 KB Output is correct
6 Correct 5 ms 528 KB Output is correct
7 Correct 19 ms 600 KB Output is correct
8 Correct 76 ms 856 KB Output is correct
9 Correct 318 ms 1104 KB Output is correct
10 Correct 2 ms 344 KB Output is correct
11 Correct 127 ms 884 KB Output is correct
12 Correct 249 ms 1076 KB Output is correct
13 Correct 165 ms 1112 KB Output is correct
14 Correct 202 ms 1020 KB Output is correct
15 Execution timed out 1282 ms 1880 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 2 ms 344 KB Output is correct
6 Correct 5 ms 528 KB Output is correct
7 Correct 19 ms 600 KB Output is correct
8 Correct 76 ms 856 KB Output is correct
9 Correct 318 ms 1104 KB Output is correct
10 Correct 2 ms 344 KB Output is correct
11 Correct 127 ms 884 KB Output is correct
12 Correct 249 ms 1076 KB Output is correct
13 Correct 165 ms 1112 KB Output is correct
14 Correct 202 ms 1020 KB Output is correct
15 Execution timed out 1282 ms 1880 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 2 ms 344 KB Output is correct
6 Correct 5 ms 528 KB Output is correct
7 Correct 19 ms 600 KB Output is correct
8 Correct 76 ms 856 KB Output is correct
9 Correct 318 ms 1104 KB Output is correct
10 Correct 2 ms 344 KB Output is correct
11 Correct 127 ms 884 KB Output is correct
12 Correct 249 ms 1076 KB Output is correct
13 Correct 165 ms 1112 KB Output is correct
14 Correct 202 ms 1020 KB Output is correct
15 Execution timed out 1282 ms 1880 KB Time limit exceeded
16 Halted 0 ms 0 KB -