oj.uz

Submission #795598

# Submission time Handle Problem Language Result Execution time Memory
795598 2023-07-27T11:34:43 Z SlavicG Minerals (JOI19_minerals) C++17
40 / 100
 200 ms 5652 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;
        vector<int> ids[n + 1];
        for(int i = 0; i < n; ++i) {
            if(l[i] <= r[i]) {
                int mid = l[i] + r[i] >> 1;
                b.push_back({mid, i});
                ids[mid].push_back(i);
            }
        }
        if(b.empty()) break;
        sort(all(b));
        int cost1 = 0, cost2 = 0;
        {
            map<int, int> vis;
            int k = j;
            while(k > b[0].first) {
                vis[k] = true;
                ++cost1;
                --k;
                vis[k] = true;
            }
            if(!vis[b.back().first]) {
                while(k < b.back().first) {
                    ++k;
                    ++cost1;
                }
            }
        }
        {
            int k = j;
            map<int, int> vis;
            while(k < b.back().first) {
                vis[k] = true;
                ++cost2;
                ++k;
                vis[k] = true;
            }
            if(!vis[b[0].first]) {
                while(k > b[0].first) {
                    --k;
                    ++cost2;
                }
            }
        }
        if(cost1 < cost2 || (cost1 == cost2) && rng() % 2) {
            map<int, int> vis;
            while(j > b[0].first) {
                if(!vis[j]) {
                    for(auto x: ids[j]) {
                        int mid = j;
                        int ans = Query(p2[x]);
                        if(ans == prevans) {
                            pr[x] = mid;
                            r[x] = mid - 1;
                        } else {
                            l[x] = mid + 1;
                        }
                        prevans = ans;
                    }
                    vis[j] = true;
                }
                prevans = Query(p1[j]);
                --j;
                if(!vis[j]) {
                    for(auto x: ids[j]) {
                        int mid = j;
                        int ans = Query(p2[x]);
                        if(ans == prevans) {
                            pr[x] = mid;
                            r[x] = mid - 1;
                        } else {
                            l[x] = mid + 1;
                        }
                        prevans = ans;
                    }
                    vis[j] = true;
                }
            }
            if(!vis[b.back().first]) {
                while(j < b.back().first) {
                    if(!vis[j]) {
                        for(auto x: ids[j]) {
                            int mid = j;
                            int ans = Query(p2[x]);
                            if(ans == prevans) {
                                pr[x] = mid;
                                r[x] = mid - 1;
                            } else {
                                l[x] = mid + 1;
                            }
                            prevans = ans;
                        }
                        vis[j] = true;
                    }
                    ++j;
                    prevans = Query(p1[j]);
                    if(!vis[j]) {
                        for(auto x: ids[j]) {
                            int mid = j;
                            int ans = Query(p2[x]);
                            if(ans == prevans) {
                                pr[x] = mid;
                                r[x] = mid - 1;
                            } else {
                                l[x] = mid + 1;
                            }
                            prevans = ans;
                        }
                        vis[j] = true;
                    }
                }
            }
        } else {
            map<int, int> vis;
            while(j < b.back().first) {
                if(!vis[j]) {
                    for(auto x: ids[j]) {
                        int mid = j;
                        int ans = Query(p2[x]);
                        if(ans == prevans) {
                            pr[x] = mid;
                            r[x] = mid - 1;
                        } else {
                            l[x] = mid + 1;
                        }
                        prevans = ans;
                    }
                    vis[j] = true;
                }
                ++j;
                prevans = Query(p1[j]);
                if(!vis[j]) {
                    for(auto x: ids[j]) {
                        int mid = j;
                        int ans = Query(p2[x]);
                        if(ans == prevans) {
                            pr[x] = mid;
                            r[x] = mid - 1;
                        } else {
                            l[x] = mid + 1;
                        }
                        prevans = ans;
                    }
                    vis[j] = true;
                }
            }
            if(!vis[b[0].first]) {
                while(j > b[0].first) {
                    if(!vis[j]) {
                        for(auto x: ids[j]) {
                            int mid = j;
                            int ans = Query(p2[x]);
                            if(ans == prevans) {
                                pr[x] = mid;
                                r[x] = mid - 1;
                            } else {
                                l[x] = mid + 1;
                            }
                            prevans = ans;
                        }
                        vis[j] = true;
                    }
                    prevans = Query(p1[j]);
                    --j;
                    if(!vis[j]) {
                        for(auto x: ids[j]) {
                            int mid = j;
                            int ans = Query(p2[x]);
                            if(ans == prevans) {
                                pr[x] = mid;
                                r[x] = mid - 1;
                            } else {
                                l[x] = mid + 1;
                            }
                            prevans = ans;
                        }
                        vis[j] = true;
                    }
                }
            }
        }
    }
    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:59:32: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   59 |                 int mid = l[i] + r[i] >> 1;
minerals.cpp:99:46: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   99 |         if(cost1 < cost2 || (cost1 == cost2) && rng() % 2) {
      |                             ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
minerals.cpp:28:9: warning: unused variable 'IN' [-Wunused-variable]
   28 |     int IN = 1;
      |         ^~
minerals.cpp:52:9: warning: unused variable 'F' [-Wunused-variable]
   52 |     int F = 0;
      |         ^

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 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 3 ms 464 KB Output is correct
2 Correct 6 ms 592 KB Output is correct
3 Correct 14 ms 844 KB Output is correct
4 Correct 33 ms 1448 KB Output is correct
5 Correct 76 ms 2432 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 0 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 3 ms 464 KB Output is correct
6 Correct 6 ms 592 KB Output is correct
7 Correct 14 ms 844 KB Output is correct
8 Correct 33 ms 1448 KB Output is correct
9 Correct 76 ms 2432 KB Output is correct
10 Correct 3 ms 464 KB Output is correct
11 Correct 44 ms 1804 KB Output is correct
12 Correct 81 ms 2560 KB Output is correct
13 Correct 82 ms 2532 KB Output is correct
14 Correct 80 ms 2468 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 0 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 3 ms 464 KB Output is correct
6 Correct 6 ms 592 KB Output is correct
7 Correct 14 ms 844 KB Output is correct
8 Correct 33 ms 1448 KB Output is correct
9 Correct 76 ms 2432 KB Output is correct
10 Correct 3 ms 464 KB Output is correct
11 Correct 44 ms 1804 KB Output is correct
12 Correct 81 ms 2560 KB Output is correct
13 Correct 82 ms 2532 KB Output is correct
14 Correct 80 ms 2468 KB Output is correct
15 Incorrect 200 ms 5652 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 0 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 3 ms 464 KB Output is correct
6 Correct 6 ms 592 KB Output is correct
7 Correct 14 ms 844 KB Output is correct
8 Correct 33 ms 1448 KB Output is correct
9 Correct 76 ms 2432 KB Output is correct
10 Correct 3 ms 464 KB Output is correct
11 Correct 44 ms 1804 KB Output is correct
12 Correct 81 ms 2560 KB Output is correct
13 Correct 82 ms 2532 KB Output is correct
14 Correct 80 ms 2468 KB Output is correct
15 Incorrect 200 ms 5652 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 0 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 3 ms 464 KB Output is correct
6 Correct 6 ms 592 KB Output is correct
7 Correct 14 ms 844 KB Output is correct
8 Correct 33 ms 1448 KB Output is correct
9 Correct 76 ms 2432 KB Output is correct
10 Correct 3 ms 464 KB Output is correct
11 Correct 44 ms 1804 KB Output is correct
12 Correct 81 ms 2560 KB Output is correct
13 Correct 82 ms 2532 KB Output is correct
14 Correct 80 ms 2468 KB Output is correct
15 Incorrect 200 ms 5652 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 0 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 3 ms 464 KB Output is correct
6 Correct 6 ms 592 KB Output is correct
7 Correct 14 ms 844 KB Output is correct
8 Correct 33 ms 1448 KB Output is correct
9 Correct 76 ms 2432 KB Output is correct
10 Correct 3 ms 464 KB Output is correct
11 Correct 44 ms 1804 KB Output is correct
12 Correct 81 ms 2560 KB Output is correct
13 Correct 82 ms 2532 KB Output is correct
14 Correct 80 ms 2468 KB Output is correct
15 Incorrect 200 ms 5652 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 0 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 3 ms 464 KB Output is correct
6 Correct 6 ms 592 KB Output is correct
7 Correct 14 ms 844 KB Output is correct
8 Correct 33 ms 1448 KB Output is correct
9 Correct 76 ms 2432 KB Output is correct
10 Correct 3 ms 464 KB Output is correct
11 Correct 44 ms 1804 KB Output is correct
12 Correct 81 ms 2560 KB Output is correct
13 Correct 82 ms 2532 KB Output is correct
14 Correct 80 ms 2468 KB Output is correct
15 Incorrect 200 ms 5652 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 0 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 3 ms 464 KB Output is correct
6 Correct 6 ms 592 KB Output is correct
7 Correct 14 ms 844 KB Output is correct
8 Correct 33 ms 1448 KB Output is correct
9 Correct 76 ms 2432 KB Output is correct
10 Correct 3 ms 464 KB Output is correct
11 Correct 44 ms 1804 KB Output is correct
12 Correct 81 ms 2560 KB Output is correct
13 Correct 82 ms 2532 KB Output is correct
14 Correct 80 ms 2468 KB Output is correct
15 Incorrect 200 ms 5652 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -