oj.uz

Submission #795538

# Submission time Handle Problem Language Result Execution time Memory
795538 2023-07-27T11:04:28 Z SlavicG Minerals (JOI19_minerals) C++17
40 / 100
 69 ms 3168 KB 
#include <bits/stdc++.h>
#include "minerals.h"
using namespace std;

#define all(v) v.begin(), v.end()
#define sz(a) (int)a.size()
#define pb push_back
#define rall(v) v.rbegin(),v.rend()

mt19937 rng(69);
void Solve(int n) {
    vector<int> p1, p2;
    int ans = 0, prevans = -1;
    vector<int> bulanea(2 * n);
    iota(bulanea.begin(), bulanea.end(), 1);
    shuffle(bulanea.begin(), bulanea.end(), rng);
    for(int i: bulanea) {
        ans = Query(i);
        if(ans == prevans) {
            p2.pb(i);
        } else {
            p1.pb(i);
        }
        prevans = ans;
    }
    assert(sz(p1) == n && sz(p2) == n);
    vector<int> pr(n, 0);
    int IN = 1;
    /*
    vector<bool> bagat(n, 1);
    for(int bit = 0; (1 << bit) < n; ++bit) {
        for(int i = 0; i < n; ++i) {
            if(i >> bit & 1) {
                if(!bagat[i]) prevans = Query(p1[i]);
                bagat[i] = 1;
            } else {
                if(bagat[i]) prevans = Query(p1[i]);
                bagat[i] = 0;
            }
        }   
        for(int i = 0; i < n; ++i) {
            int ans = Query(p2[i]);
            if(ans == prevans) {
                pr[i] += (1 << bit);
            }
            prevans = ans;
        }
        IN ^= 1;
    }
    */
    vector<int> l(n, 0), r(n, n - 1);
    int F = 0;
    int j = n - 1;
    for(int runs = 0; runs < 17; ++runs) {
        vector<pair<int, int>> b;
        for(int i = 0; i < n; ++i) {
            if(l[i] <= r[i]) {
                int mid = l[i] + r[i] >> 1;
                b.push_back({mid, i});
            }
        }
        if(!F) {
            sort(rall(b));
        } else {
            sort(all(b));
        }

        for(auto x: b) {
            int mid = x.first;
            while(j > mid) {
                prevans = Query(p1[j]);
                --j;
            }
            while(j < mid) {
                ++j;
                prevans = Query(p1[j]);
            }
            int ans = Query(p2[x.second]);
            if(ans == prevans) {
                pr[x.second] = mid;
                r[x.second] = mid - 1;
            } else {
                l[x.second] = mid + 1;
            }
            prevans = ans;
        }
        F ^= 1;
    }
    for(int i = 0; i < n; ++i) {
        Answer(p2[i], p1[pr[i]]);
    }
}
/*
4
1 5
2 6
3 4
7 8
*/

Compilation message

minerals.cpp: In function 'void Solve(int)':
minerals.cpp:58:32: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   58 |                 int mid = l[i] + r[i] >> 1;
minerals.cpp:28:9: warning: unused variable 'IN' [-Wunused-variable]
   28 |     int IN = 1;
      |         ^~

Subtask #1
6.0 / 6.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 3 ms 336 KB Output is correct
3 Correct 5 ms 576 KB Output is correct
4 Correct 11 ms 848 KB Output is correct
5 Correct 25 ms 1252 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 3 ms 336 KB Output is correct
7 Correct 5 ms 576 KB Output is correct
8 Correct 11 ms 848 KB Output is correct
9 Correct 25 ms 1252 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 15 ms 1052 KB Output is correct
12 Correct 25 ms 1376 KB Output is correct
13 Correct 26 ms 1336 KB Output is correct
14 Correct 25 ms 1288 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 3 ms 336 KB Output is correct
7 Correct 5 ms 576 KB Output is correct
8 Correct 11 ms 848 KB Output is correct
9 Correct 25 ms 1252 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 15 ms 1052 KB Output is correct
12 Correct 25 ms 1376 KB Output is correct
13 Correct 26 ms 1336 KB Output is correct
14 Correct 25 ms 1288 KB Output is correct
15 Incorrect 69 ms 3168 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 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 3 ms 336 KB Output is correct
7 Correct 5 ms 576 KB Output is correct
8 Correct 11 ms 848 KB Output is correct
9 Correct 25 ms 1252 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 15 ms 1052 KB Output is correct
12 Correct 25 ms 1376 KB Output is correct
13 Correct 26 ms 1336 KB Output is correct
14 Correct 25 ms 1288 KB Output is correct
15 Incorrect 69 ms 3168 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 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 3 ms 336 KB Output is correct
7 Correct 5 ms 576 KB Output is correct
8 Correct 11 ms 848 KB Output is correct
9 Correct 25 ms 1252 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 15 ms 1052 KB Output is correct
12 Correct 25 ms 1376 KB Output is correct
13 Correct 26 ms 1336 KB Output is correct
14 Correct 25 ms 1288 KB Output is correct
15 Incorrect 69 ms 3168 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 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 3 ms 336 KB Output is correct
7 Correct 5 ms 576 KB Output is correct
8 Correct 11 ms 848 KB Output is correct
9 Correct 25 ms 1252 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 15 ms 1052 KB Output is correct
12 Correct 25 ms 1376 KB Output is correct
13 Correct 26 ms 1336 KB Output is correct
14 Correct 25 ms 1288 KB Output is correct
15 Incorrect 69 ms 3168 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 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 3 ms 336 KB Output is correct
7 Correct 5 ms 576 KB Output is correct
8 Correct 11 ms 848 KB Output is correct
9 Correct 25 ms 1252 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 15 ms 1052 KB Output is correct
12 Correct 25 ms 1376 KB Output is correct
13 Correct 26 ms 1336 KB Output is correct
14 Correct 25 ms 1288 KB Output is correct
15 Incorrect 69 ms 3168 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 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 3 ms 336 KB Output is correct
7 Correct 5 ms 576 KB Output is correct
8 Correct 11 ms 848 KB Output is correct
9 Correct 25 ms 1252 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 15 ms 1052 KB Output is correct
12 Correct 25 ms 1376 KB Output is correct
13 Correct 26 ms 1336 KB Output is correct
14 Correct 25 ms 1288 KB Output is correct
15 Incorrect 69 ms 3168 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -