oj.uz

Submission #909976

# Submission time Handle Problem Language Result Execution time Memory
909976 2024-01-17T17:10:35 Z guechotjrhh Minerals (JOI19_minerals) C++14
70 / 100
 66 ms 3668 KB 
#include "minerals.h"
#include<vector>
#include<set>
#include<random>
#include<algorithm>
#include<iostream>
using namespace std;

int n, s;
//2nlog(2n)
random_device rd;
mt19937 g(rd());
int szdp = 10000;
vector<int> dp0(szdp + 1),nxt0(szdp + 1), dp1(szdp+1), nxt1(szdp+1);

void solve(vector<int>& in, vector<int>& rest, int flag) {
    //cout << "solve "<< in.size() << ' ' << rest.size() << ' ' << flag << endl;
    //shuffle(in.begin(), in.end(), g);
    //shuffle(rest.begin(), rest.end(), g);
    if (in.size() == 1) { Answer(in[0], rest[0]); return; }
    
    //better cut - not 1/2
    vector<int> in1, in2;
    //int sz1 = in.size() - nxt1[in.size()];
    int sz1 = 2 * in.size() / 3;
    if (in.size() <= szdp) {
        if (flag) sz1 = in.size() - nxt1[in.size()];
        else sz1 = in.size() - nxt0[in.size()];
    }

    for (int i = 0; i < sz1; i++) in1.push_back(in[i]);
    for (int i = sz1; i < in.size(); i++) in2.push_back(in[i]);
    
    //get rest for in1. possible better - not to take out right away
    int sz = 0;
    for (int i : in2) sz = Query(i);
    vector<int> rest1, rest2;
    for (int j : rest) {
        //if (rest1.size() == in1.size()) { rest2.push_back(j); continue; }
        //if (rest2.size() == in2.size()) { rest1.push_back(j); continue; }

        int u = Query(j);
        if (u == sz) rest1.push_back(j);
        else {
            rest2.push_back(j);
            sz = u;
            //Query(j);
        }
    }
    solve(in1, rest1, 1 - flag);
    if (flag==0) solve(rest2, in2, 0);
    else {
        for (int i : in2) Query(i);
        solve(in2, rest2, 0);
    }
}

void Solve(int N) {
    dp0[1] = dp1[1] = 0;
    for (int i = 2; i <= szdp; i++) {
        dp0[i] = dp1[i] = 1e9;
        for (int j = 1; j <= i / 2; j++) {
            if (dp0[j] + dp1[i - j] + j + i < dp0[i]) {
                dp0[i] = dp0[j] + dp1[i - j] + j + i;
                nxt0[i] = j;
            }
            if (dp0[j] + dp0[i - j] + 2*j + i < dp1[i]) {
                dp1[i] = dp0[j] + dp0[i - j] + 2 * j + i;
                nxt1[i] = j;
            }
        }
    }
    /*for (int i = 2; i <= szdp; i++) {
        int l = 1, r = i / 2, m;
        while (r > l) {
            m = (l + r) / 2;
            int vm = dp1[m] + dp1[i - m] + 2 * m + i;
            int vm1 = dp1[m+1] + dp1[i - m - 1] + 2 * m + 2 + i;
            if (vm > vm1) l = m + 1;
            else r = m;
        }
        dp1[i] = dp1[l] + dp1[i - l] + 2 * l + i;
        nxt1[i] = l;
        //if (dp1[i] != dp[i]) { cout << i << ' ' << dp[i] << ' ' << dp1[i] << ' ' << "ERROR!!!" << endl; break; }
    }
    cout << dp1[N] + N << endl;*/
    n = N; s = n << 1;
    int sz = 0;
    vector<int> in, rest;
    vector<int> vec(s);
    for (int i = 0; i < s; i++)vec[i] = i + 1;
    shuffle(vec.begin(), vec.end(), g);
    for (int i : vec) {
        //if (in.size() < n) {
            int u = Query(i);
            if (u > sz) {
                sz = u;
                in.push_back(i);
            }
            else {
                rest.push_back(i);
            }
        
    }
    solve(in, rest, 1);
}

Compilation message

minerals.cpp: In function 'void solve(std::vector<int>&, std::vector<int>&, int)':
minerals.cpp:26:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   26 |     if (in.size() <= szdp) {
      |         ~~~~~~~~~~^~~~~~~
minerals.cpp:32:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for (int i = sz1; i < in.size(); i++) in2.push_back(in[i]);
      |                       ~~^~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 600 KB Output is correct
2 Correct 35 ms 592 KB Output is correct
3 Correct 38 ms 600 KB Output is correct
4 Correct 35 ms 600 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 600 KB Output is correct
2 Correct 37 ms 600 KB Output is correct
3 Correct 42 ms 868 KB Output is correct
4 Correct 40 ms 1112 KB Output is correct
5 Correct 44 ms 1744 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 600 KB Output is correct
2 Correct 35 ms 592 KB Output is correct
3 Correct 38 ms 600 KB Output is correct
4 Correct 35 ms 600 KB Output is correct
5 Correct 39 ms 600 KB Output is correct
6 Correct 37 ms 600 KB Output is correct
7 Correct 42 ms 868 KB Output is correct
8 Correct 40 ms 1112 KB Output is correct
9 Correct 44 ms 1744 KB Output is correct
10 Correct 36 ms 600 KB Output is correct
11 Correct 43 ms 1424 KB Output is correct
12 Correct 48 ms 1616 KB Output is correct
13 Correct 45 ms 1616 KB Output is correct
14 Correct 44 ms 1976 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 600 KB Output is correct
2 Correct 35 ms 592 KB Output is correct
3 Correct 38 ms 600 KB Output is correct
4 Correct 35 ms 600 KB Output is correct
5 Correct 39 ms 600 KB Output is correct
6 Correct 37 ms 600 KB Output is correct
7 Correct 42 ms 868 KB Output is correct
8 Correct 40 ms 1112 KB Output is correct
9 Correct 44 ms 1744 KB Output is correct
10 Correct 36 ms 600 KB Output is correct
11 Correct 43 ms 1424 KB Output is correct
12 Correct 48 ms 1616 KB Output is correct
13 Correct 45 ms 1616 KB Output is correct
14 Correct 44 ms 1976 KB Output is correct
15 Correct 60 ms 3408 KB Output is correct
16 Correct 66 ms 3440 KB Output is correct
17 Correct 60 ms 3668 KB Output is correct
18 Correct 63 ms 3640 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 600 KB Output is correct
2 Correct 35 ms 592 KB Output is correct
3 Correct 38 ms 600 KB Output is correct
4 Correct 35 ms 600 KB Output is correct
5 Correct 39 ms 600 KB Output is correct
6 Correct 37 ms 600 KB Output is correct
7 Correct 42 ms 868 KB Output is correct
8 Correct 40 ms 1112 KB Output is correct
9 Correct 44 ms 1744 KB Output is correct
10 Correct 36 ms 600 KB Output is correct
11 Correct 43 ms 1424 KB Output is correct
12 Correct 48 ms 1616 KB Output is correct
13 Correct 45 ms 1616 KB Output is correct
14 Correct 44 ms 1976 KB Output is correct
15 Correct 60 ms 3408 KB Output is correct
16 Correct 66 ms 3440 KB Output is correct
17 Correct 60 ms 3668 KB Output is correct
18 Correct 63 ms 3640 KB Output is correct
19 Incorrect 61 ms 3448 KB Wrong Answer [2]
20 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 600 KB Output is correct
2 Correct 35 ms 592 KB Output is correct
3 Correct 38 ms 600 KB Output is correct
4 Correct 35 ms 600 KB Output is correct
5 Correct 39 ms 600 KB Output is correct
6 Correct 37 ms 600 KB Output is correct
7 Correct 42 ms 868 KB Output is correct
8 Correct 40 ms 1112 KB Output is correct
9 Correct 44 ms 1744 KB Output is correct
10 Correct 36 ms 600 KB Output is correct
11 Correct 43 ms 1424 KB Output is correct
12 Correct 48 ms 1616 KB Output is correct
13 Correct 45 ms 1616 KB Output is correct
14 Correct 44 ms 1976 KB Output is correct
15 Correct 60 ms 3408 KB Output is correct
16 Correct 66 ms 3440 KB Output is correct
17 Correct 60 ms 3668 KB Output is correct
18 Correct 63 ms 3640 KB Output is correct
19 Incorrect 61 ms 3448 KB Wrong Answer [2]
20 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 600 KB Output is correct
2 Correct 35 ms 592 KB Output is correct
3 Correct 38 ms 600 KB Output is correct
4 Correct 35 ms 600 KB Output is correct
5 Correct 39 ms 600 KB Output is correct
6 Correct 37 ms 600 KB Output is correct
7 Correct 42 ms 868 KB Output is correct
8 Correct 40 ms 1112 KB Output is correct
9 Correct 44 ms 1744 KB Output is correct
10 Correct 36 ms 600 KB Output is correct
11 Correct 43 ms 1424 KB Output is correct
12 Correct 48 ms 1616 KB Output is correct
13 Correct 45 ms 1616 KB Output is correct
14 Correct 44 ms 1976 KB Output is correct
15 Correct 60 ms 3408 KB Output is correct
16 Correct 66 ms 3440 KB Output is correct
17 Correct 60 ms 3668 KB Output is correct
18 Correct 63 ms 3640 KB Output is correct
19 Incorrect 61 ms 3448 KB Wrong Answer [2]
20 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 600 KB Output is correct
2 Correct 35 ms 592 KB Output is correct
3 Correct 38 ms 600 KB Output is correct
4 Correct 35 ms 600 KB Output is correct
5 Correct 39 ms 600 KB Output is correct
6 Correct 37 ms 600 KB Output is correct
7 Correct 42 ms 868 KB Output is correct
8 Correct 40 ms 1112 KB Output is correct
9 Correct 44 ms 1744 KB Output is correct
10 Correct 36 ms 600 KB Output is correct
11 Correct 43 ms 1424 KB Output is correct
12 Correct 48 ms 1616 KB Output is correct
13 Correct 45 ms 1616 KB Output is correct
14 Correct 44 ms 1976 KB Output is correct
15 Correct 60 ms 3408 KB Output is correct
16 Correct 66 ms 3440 KB Output is correct
17 Correct 60 ms 3668 KB Output is correct
18 Correct 63 ms 3640 KB Output is correct
19 Incorrect 61 ms 3448 KB Wrong Answer [2]
20 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 600 KB Output is correct
2 Correct 35 ms 592 KB Output is correct
3 Correct 38 ms 600 KB Output is correct
4 Correct 35 ms 600 KB Output is correct
5 Correct 39 ms 600 KB Output is correct
6 Correct 37 ms 600 KB Output is correct
7 Correct 42 ms 868 KB Output is correct
8 Correct 40 ms 1112 KB Output is correct
9 Correct 44 ms 1744 KB Output is correct
10 Correct 36 ms 600 KB Output is correct
11 Correct 43 ms 1424 KB Output is correct
12 Correct 48 ms 1616 KB Output is correct
13 Correct 45 ms 1616 KB Output is correct
14 Correct 44 ms 1976 KB Output is correct
15 Correct 60 ms 3408 KB Output is correct
16 Correct 66 ms 3440 KB Output is correct
17 Correct 60 ms 3668 KB Output is correct
18 Correct 63 ms 3640 KB Output is correct
19 Incorrect 61 ms 3448 KB Wrong Answer [2]
20 Halted 0 ms 0 KB -