oj.uz

Submission #795585

# Submission time Handle Problem Language Result Execution time Memory
795585 2023-07-27T11:30:03 Z SlavicG Minerals (JOI19_minerals) C++17
40 / 100
 201 ms 5800 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) {
            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: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 564 KB Output is correct
3 Correct 14 ms 848 KB Output is correct
4 Correct 33 ms 1480 KB Output is correct
5 Correct 72 ms 2540 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 564 KB Output is correct
7 Correct 14 ms 848 KB Output is correct
8 Correct 33 ms 1480 KB Output is correct
9 Correct 72 ms 2540 KB Output is correct
10 Correct 4 ms 464 KB Output is correct
11 Correct 54 ms 1752 KB Output is correct
12 Correct 86 ms 2556 KB Output is correct
13 Correct 76 ms 2532 KB Output is correct
14 Correct 80 ms 2448 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 564 KB Output is correct
7 Correct 14 ms 848 KB Output is correct
8 Correct 33 ms 1480 KB Output is correct
9 Correct 72 ms 2540 KB Output is correct
10 Correct 4 ms 464 KB Output is correct
11 Correct 54 ms 1752 KB Output is correct
12 Correct 86 ms 2556 KB Output is correct
13 Correct 76 ms 2532 KB Output is correct
14 Correct 80 ms 2448 KB Output is correct
15 Incorrect 201 ms 5800 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 564 KB Output is correct
7 Correct 14 ms 848 KB Output is correct
8 Correct 33 ms 1480 KB Output is correct
9 Correct 72 ms 2540 KB Output is correct
10 Correct 4 ms 464 KB Output is correct
11 Correct 54 ms 1752 KB Output is correct
12 Correct 86 ms 2556 KB Output is correct
13 Correct 76 ms 2532 KB Output is correct
14 Correct 80 ms 2448 KB Output is correct
15 Incorrect 201 ms 5800 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 564 KB Output is correct
7 Correct 14 ms 848 KB Output is correct
8 Correct 33 ms 1480 KB Output is correct
9 Correct 72 ms 2540 KB Output is correct
10 Correct 4 ms 464 KB Output is correct
11 Correct 54 ms 1752 KB Output is correct
12 Correct 86 ms 2556 KB Output is correct
13 Correct 76 ms 2532 KB Output is correct
14 Correct 80 ms 2448 KB Output is correct
15 Incorrect 201 ms 5800 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 564 KB Output is correct
7 Correct 14 ms 848 KB Output is correct
8 Correct 33 ms 1480 KB Output is correct
9 Correct 72 ms 2540 KB Output is correct
10 Correct 4 ms 464 KB Output is correct
11 Correct 54 ms 1752 KB Output is correct
12 Correct 86 ms 2556 KB Output is correct
13 Correct 76 ms 2532 KB Output is correct
14 Correct 80 ms 2448 KB Output is correct
15 Incorrect 201 ms 5800 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 564 KB Output is correct
7 Correct 14 ms 848 KB Output is correct
8 Correct 33 ms 1480 KB Output is correct
9 Correct 72 ms 2540 KB Output is correct
10 Correct 4 ms 464 KB Output is correct
11 Correct 54 ms 1752 KB Output is correct
12 Correct 86 ms 2556 KB Output is correct
13 Correct 76 ms 2532 KB Output is correct
14 Correct 80 ms 2448 KB Output is correct
15 Incorrect 201 ms 5800 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 564 KB Output is correct
7 Correct 14 ms 848 KB Output is correct
8 Correct 33 ms 1480 KB Output is correct
9 Correct 72 ms 2540 KB Output is correct
10 Correct 4 ms 464 KB Output is correct
11 Correct 54 ms 1752 KB Output is correct
12 Correct 86 ms 2556 KB Output is correct
13 Correct 76 ms 2532 KB Output is correct
14 Correct 80 ms 2448 KB Output is correct
15 Incorrect 201 ms 5800 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -