oj.uz

Submission #795545

# Submission time Handle Problem Language Result Execution time Memory
795545 2023-07-27T11:09:45 Z SlavicG Minerals (JOI19_minerals) C++17
40 / 100
 84 ms 3072 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});
            }
        }
        int k = j;
        int cost1 = 0, cost2 = 0;
        sort(all(b));
        for(auto x: b) {
            int mid = x.first;
            while(k > mid) {
                --k;
                ++cost1;
            }
            while(k < mid) {
                ++k;
                ++cost1;
            }
        }
        k = j;
        sort(rall(b));
        for(auto x: b) {
            int mid = x.first;
            while(k > mid) {
                --k;
                ++cost2;
            }
            while(k < mid) {
                ++k;
                ++cost2;
            }
        }

        if(cost1 <= cost2) sort(all(b));
        else sort(rall(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 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 1 ms 208 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 336 KB Output is correct
2 Correct 3 ms 336 KB Output is correct
3 Correct 6 ms 592 KB Output is correct
4 Correct 14 ms 840 KB Output is correct
5 Correct 30 ms 1288 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 2 ms 336 KB Output is correct
6 Correct 3 ms 336 KB Output is correct
7 Correct 6 ms 592 KB Output is correct
8 Correct 14 ms 840 KB Output is correct
9 Correct 30 ms 1288 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 21 ms 1064 KB Output is correct
12 Correct 31 ms 1316 KB Output is correct
13 Correct 29 ms 1304 KB Output is correct
14 Correct 30 ms 1264 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 2 ms 336 KB Output is correct
6 Correct 3 ms 336 KB Output is correct
7 Correct 6 ms 592 KB Output is correct
8 Correct 14 ms 840 KB Output is correct
9 Correct 30 ms 1288 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 21 ms 1064 KB Output is correct
12 Correct 31 ms 1316 KB Output is correct
13 Correct 29 ms 1304 KB Output is correct
14 Correct 30 ms 1264 KB Output is correct
15 Incorrect 84 ms 3072 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 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 2 ms 336 KB Output is correct
6 Correct 3 ms 336 KB Output is correct
7 Correct 6 ms 592 KB Output is correct
8 Correct 14 ms 840 KB Output is correct
9 Correct 30 ms 1288 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 21 ms 1064 KB Output is correct
12 Correct 31 ms 1316 KB Output is correct
13 Correct 29 ms 1304 KB Output is correct
14 Correct 30 ms 1264 KB Output is correct
15 Incorrect 84 ms 3072 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 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 2 ms 336 KB Output is correct
6 Correct 3 ms 336 KB Output is correct
7 Correct 6 ms 592 KB Output is correct
8 Correct 14 ms 840 KB Output is correct
9 Correct 30 ms 1288 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 21 ms 1064 KB Output is correct
12 Correct 31 ms 1316 KB Output is correct
13 Correct 29 ms 1304 KB Output is correct
14 Correct 30 ms 1264 KB Output is correct
15 Incorrect 84 ms 3072 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 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 2 ms 336 KB Output is correct
6 Correct 3 ms 336 KB Output is correct
7 Correct 6 ms 592 KB Output is correct
8 Correct 14 ms 840 KB Output is correct
9 Correct 30 ms 1288 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 21 ms 1064 KB Output is correct
12 Correct 31 ms 1316 KB Output is correct
13 Correct 29 ms 1304 KB Output is correct
14 Correct 30 ms 1264 KB Output is correct
15 Incorrect 84 ms 3072 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 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 2 ms 336 KB Output is correct
6 Correct 3 ms 336 KB Output is correct
7 Correct 6 ms 592 KB Output is correct
8 Correct 14 ms 840 KB Output is correct
9 Correct 30 ms 1288 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 21 ms 1064 KB Output is correct
12 Correct 31 ms 1316 KB Output is correct
13 Correct 29 ms 1304 KB Output is correct
14 Correct 30 ms 1264 KB Output is correct
15 Incorrect 84 ms 3072 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 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 2 ms 336 KB Output is correct
6 Correct 3 ms 336 KB Output is correct
7 Correct 6 ms 592 KB Output is correct
8 Correct 14 ms 840 KB Output is correct
9 Correct 30 ms 1288 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 21 ms 1064 KB Output is correct
12 Correct 31 ms 1316 KB Output is correct
13 Correct 29 ms 1304 KB Output is correct
14 Correct 30 ms 1264 KB Output is correct
15 Incorrect 84 ms 3072 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -