oj.uz

Submission #909846

# Submission time Handle Problem Language Result Execution time Memory
909846 2024-01-17T13:25:31 Z guechotjrhh Minerals (JOI19_minerals) C++14
40 / 100
 47 ms 3492 KB 
#include "minerals.h"
#include<vector>
#include<set>
#include<random>
#include<algorithm>
using namespace std;

int n, s;
//2nlog(2n)
random_device rd;
mt19937 g(rd());

void solve(vector<int>& in, vector<int>& rest) {
    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 = 5 * in.size() / 7;
    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);
    for (int i : in2) Query(i);
    solve(in2, rest2);
}

void Solve(int N) {
    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);
            }
        }
        else {
            rest.push_back(i);
        }
    }
    solve(in, rest);
}

Compilation message

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

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 1 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 2 ms 600 KB Output is correct
3 Correct 4 ms 780 KB Output is correct
4 Correct 9 ms 1112 KB Output is correct
5 Correct 16 ms 1568 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 1 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 2 ms 600 KB Output is correct
7 Correct 4 ms 780 KB Output is correct
8 Correct 9 ms 1112 KB Output is correct
9 Correct 16 ms 1568 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 13 ms 1024 KB Output is correct
12 Correct 16 ms 1572 KB Output is correct
13 Correct 17 ms 1516 KB Output is correct
14 Correct 16 ms 1624 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 1 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 2 ms 600 KB Output is correct
7 Correct 4 ms 780 KB Output is correct
8 Correct 9 ms 1112 KB Output is correct
9 Correct 16 ms 1568 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 13 ms 1024 KB Output is correct
12 Correct 16 ms 1572 KB Output is correct
13 Correct 17 ms 1516 KB Output is correct
14 Correct 16 ms 1624 KB Output is correct
15 Incorrect 47 ms 3492 KB Wrong Answer [2]
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 1 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 2 ms 600 KB Output is correct
7 Correct 4 ms 780 KB Output is correct
8 Correct 9 ms 1112 KB Output is correct
9 Correct 16 ms 1568 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 13 ms 1024 KB Output is correct
12 Correct 16 ms 1572 KB Output is correct
13 Correct 17 ms 1516 KB Output is correct
14 Correct 16 ms 1624 KB Output is correct
15 Incorrect 47 ms 3492 KB Wrong Answer [2]
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 1 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 2 ms 600 KB Output is correct
7 Correct 4 ms 780 KB Output is correct
8 Correct 9 ms 1112 KB Output is correct
9 Correct 16 ms 1568 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 13 ms 1024 KB Output is correct
12 Correct 16 ms 1572 KB Output is correct
13 Correct 17 ms 1516 KB Output is correct
14 Correct 16 ms 1624 KB Output is correct
15 Incorrect 47 ms 3492 KB Wrong Answer [2]
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 1 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 2 ms 600 KB Output is correct
7 Correct 4 ms 780 KB Output is correct
8 Correct 9 ms 1112 KB Output is correct
9 Correct 16 ms 1568 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 13 ms 1024 KB Output is correct
12 Correct 16 ms 1572 KB Output is correct
13 Correct 17 ms 1516 KB Output is correct
14 Correct 16 ms 1624 KB Output is correct
15 Incorrect 47 ms 3492 KB Wrong Answer [2]
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 1 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 2 ms 600 KB Output is correct
7 Correct 4 ms 780 KB Output is correct
8 Correct 9 ms 1112 KB Output is correct
9 Correct 16 ms 1568 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 13 ms 1024 KB Output is correct
12 Correct 16 ms 1572 KB Output is correct
13 Correct 17 ms 1516 KB Output is correct
14 Correct 16 ms 1624 KB Output is correct
15 Incorrect 47 ms 3492 KB Wrong Answer [2]
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 1 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 2 ms 600 KB Output is correct
7 Correct 4 ms 780 KB Output is correct
8 Correct 9 ms 1112 KB Output is correct
9 Correct 16 ms 1568 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 13 ms 1024 KB Output is correct
12 Correct 16 ms 1572 KB Output is correct
13 Correct 17 ms 1516 KB Output is correct
14 Correct 16 ms 1624 KB Output is correct
15 Incorrect 47 ms 3492 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -