oj.uz

Submission #250090

# Submission time Handle Problem Language Result Execution time Memory
250090 2020-07-17T01:40:05 Z dantoh000 Minerals (JOI19_minerals) C++14
40 / 100
 32 ms 2420 KB 
#include <bits/stdc++.h>
#include "minerals.h"
using namespace std;
vector<int> Q;
vector<int> P;
int ans[86005];
void solve(vector<int> p, int l, int r){
    if (r == l){
        //printf("%d -> %d\n",Q[l],p[0]);
        ans[Q[l]] = p[0];
        return;
    }
    /*printf("new\n");
    for (auto x : p){
        printf("%d ",x);
    }
    printf("<- P\n");
    for (int i = l; i <= r; i++){
        printf("%d ",Q[i]);
    }
    printf("<- Q\n");*/
    assert(p.size() == r-l+1);
    vector<int> Lp;
    vector<int> Rp;
    int n = r-l+1;
    int mid = (l+r)/2;
    int last;
    for (int i = mid+1; i <= r; i++){
        //printf("solve: removing %d\n",Q[i]);
        last = Query(Q[i]);
    }
    for (int i = 0; i < n; i++){
        //printf("solve: removing %d\n",p[i]);
        int q = Query(p[i]);
        if (q == last){
            //printf("solve: adding %d\n",p[i]);
            Query(p[i]);
            Lp.push_back(p[i]);
        }
        else{
            Rp.push_back(p[i]);
        }
       last = q;
    }
    solve(Lp, l, mid);
    for (auto x : p) {
        //printf("solve: removing/adding %d\n",x);
        Query(x);
    }
    for (int i = l; i <= r; i++) {
        //printf("solve: removing/adding %d\n",Q[i]);
        Query(Q[i]);
    }
    solve(Rp, mid+1, r);
}
void Solve(int N) {
    int last = 0;
    for (int i = 1; i <= 2*N; i++){
        int q = Query(i);
        if (q == last){
            Q.push_back(i);
        }
        else{
            P.push_back(i);
        }
        last = q;
    }
    solve(P,0,N-1);
    for (auto x: Q){
        Answer(x,ans[x]);
    }
}

Compilation message

In file included from /usr/include/c++/7/cassert:44:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:33,
                 from minerals.cpp:1:
minerals.cpp: In function 'void solve(std::vector<int>, int, int)':
minerals.cpp:22:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     assert(p.size() == r-l+1);
            ~~~~~~~~~^~~~~~~~
minerals.cpp:35:9: warning: 'last' may be used uninitialized in this function [-Wmaybe-uninitialized]
         if (q == last){
         ^~

Subtask #1
6.0 / 6.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 10 ms 800 KB Output is correct
5 Correct 27 ms 1088 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 5 ms 512 KB Output is correct
8 Correct 10 ms 800 KB Output is correct
9 Correct 27 ms 1088 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 13 ms 1008 KB Output is correct
12 Correct 20 ms 1216 KB Output is correct
13 Correct 18 ms 1244 KB Output is correct
14 Correct 17 ms 1088 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 5 ms 512 KB Output is correct
8 Correct 10 ms 800 KB Output is correct
9 Correct 27 ms 1088 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 13 ms 1008 KB Output is correct
12 Correct 20 ms 1216 KB Output is correct
13 Correct 18 ms 1244 KB Output is correct
14 Correct 17 ms 1088 KB Output is correct
15 Incorrect 32 ms 2420 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 5 ms 512 KB Output is correct
8 Correct 10 ms 800 KB Output is correct
9 Correct 27 ms 1088 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 13 ms 1008 KB Output is correct
12 Correct 20 ms 1216 KB Output is correct
13 Correct 18 ms 1244 KB Output is correct
14 Correct 17 ms 1088 KB Output is correct
15 Incorrect 32 ms 2420 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 5 ms 512 KB Output is correct
8 Correct 10 ms 800 KB Output is correct
9 Correct 27 ms 1088 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 13 ms 1008 KB Output is correct
12 Correct 20 ms 1216 KB Output is correct
13 Correct 18 ms 1244 KB Output is correct
14 Correct 17 ms 1088 KB Output is correct
15 Incorrect 32 ms 2420 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 5 ms 512 KB Output is correct
8 Correct 10 ms 800 KB Output is correct
9 Correct 27 ms 1088 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 13 ms 1008 KB Output is correct
12 Correct 20 ms 1216 KB Output is correct
13 Correct 18 ms 1244 KB Output is correct
14 Correct 17 ms 1088 KB Output is correct
15 Incorrect 32 ms 2420 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 5 ms 512 KB Output is correct
8 Correct 10 ms 800 KB Output is correct
9 Correct 27 ms 1088 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 13 ms 1008 KB Output is correct
12 Correct 20 ms 1216 KB Output is correct
13 Correct 18 ms 1244 KB Output is correct
14 Correct 17 ms 1088 KB Output is correct
15 Incorrect 32 ms 2420 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 5 ms 512 KB Output is correct
8 Correct 10 ms 800 KB Output is correct
9 Correct 27 ms 1088 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 13 ms 1008 KB Output is correct
12 Correct 20 ms 1216 KB Output is correct
13 Correct 18 ms 1244 KB Output is correct
14 Correct 17 ms 1088 KB Output is correct
15 Incorrect 32 ms 2420 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -