oj.uz

Submission #1048891

# Submission time Handle Problem Language Result Execution time Memory
1048891 2024-08-08T10:27:36 Z GrindMachine Minerals (JOI19_minerals) C++17
75 / 100
 101 ms 3860 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a,b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a,b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

/*

refs:
some other solutions

*/

const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

#include "minerals.h"

vector<pii> ans;
vector<int> best(N);

void precalc(int n){
    vector<int> dp(n+5,inf1);
    dp[1] = 0;
    for(int i = 2; i <= n; ++i){
        if(i <= 1000){
            rep1(j,i/2){
                int val = dp[j]+dp[i-j]+i+j-1;
                if(val < dp[i]){
                    dp[i] = val;
                    best[i] = j;
                }
            }   
        }
        else{
            for(int j = i/3-5; j <= i/2; ++j){
                int val = dp[j]+dp[i-j]+i+j-1;
                if(val < dp[i]){
                    dp[i] = val;
                    best[i] = j;
                }
            }
        }
    }
}

void go(vector<int> &a, vector<int> &b, ll t){
    if(a.empty()) return;
    if(sz(a) == 1){
        ans.pb({a[0],b[0]});
        return;
    }

    int mid1 = best[sz(a)];
    int mid2 = sz(a)-mid1;

    vector<int> al,ar;
    int d = 0;

    if(!t){
        rep(i,sz(a)){
            if(i < mid1){
                al.pb(a[i]);
                d = Query(a[i]);
            }
            else{
                ar.pb(a[i]);
            }
        }
    }
    else{
        rep(i,sz(a)){
            if(i < mid2){
                al.pb(a[i]);
            }
            else{
                ar.pb(a[i]);
                d = Query(a[i]);
            }
        }
    }

    vector<int> bl,br;

    rep(i,sz(b)-1){
        int x = b[i];
        int res = Query(x);
        if(res == d){
            bl.pb(x);
        }
        else{
            br.pb(x);
        }
        d = res;
    }

    int x = b.back();
    if(sz(al) != sz(bl)) bl.pb(x);
    else br.pb(x);

    go(al,bl,1);
    go(ar,br,0);
}

void Solve(int n) {
    // int v = Query(1);
    // for (int i = 1; i <= N; ++i) {
    //     Answer(i, 2 * N + 1 - i);
    // }

    precalc(n);

    vector<int> v1,v2;
    int distinct = 0;

    rep1(i,2*n){
        int x = Query(i);
        if(x == distinct+1){
            v1.pb(i);
            distinct++;
        }
        else{
            v2.pb(i);
        }
    }

    rep1(i,2*n) Query(i);
    
    go(v1,v2,0);

    for(auto [i,j] : ans){
        Answer(i,j);
    }
}

Subtask #1
6.0 / 6.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 856 KB Output is correct
2 Correct 1 ms 856 KB Output is correct
3 Correct 3 ms 1112 KB Output is correct
4 Correct 7 ms 1368 KB Output is correct
5 Correct 18 ms 1784 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 0 ms 600 KB Output is correct
3 Correct 1 ms 856 KB Output is correct
4 Correct 0 ms 856 KB Output is correct
5 Correct 1 ms 856 KB Output is correct
6 Correct 1 ms 856 KB Output is correct
7 Correct 3 ms 1112 KB Output is correct
8 Correct 7 ms 1368 KB Output is correct
9 Correct 18 ms 1784 KB Output is correct
10 Correct 1 ms 856 KB Output is correct
11 Correct 11 ms 1624 KB Output is correct
12 Correct 18 ms 1788 KB Output is correct
13 Correct 16 ms 1788 KB Output is correct
14 Correct 18 ms 1856 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 0 ms 600 KB Output is correct
3 Correct 1 ms 856 KB Output is correct
4 Correct 0 ms 856 KB Output is correct
5 Correct 1 ms 856 KB Output is correct
6 Correct 1 ms 856 KB Output is correct
7 Correct 3 ms 1112 KB Output is correct
8 Correct 7 ms 1368 KB Output is correct
9 Correct 18 ms 1784 KB Output is correct
10 Correct 1 ms 856 KB Output is correct
11 Correct 11 ms 1624 KB Output is correct
12 Correct 18 ms 1788 KB Output is correct
13 Correct 16 ms 1788 KB Output is correct
14 Correct 18 ms 1856 KB Output is correct
15 Correct 89 ms 3556 KB Output is correct
16 Correct 86 ms 3640 KB Output is correct
17 Correct 85 ms 3584 KB Output is correct
18 Correct 97 ms 3424 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 0 ms 600 KB Output is correct
3 Correct 1 ms 856 KB Output is correct
4 Correct 0 ms 856 KB Output is correct
5 Correct 1 ms 856 KB Output is correct
6 Correct 1 ms 856 KB Output is correct
7 Correct 3 ms 1112 KB Output is correct
8 Correct 7 ms 1368 KB Output is correct
9 Correct 18 ms 1784 KB Output is correct
10 Correct 1 ms 856 KB Output is correct
11 Correct 11 ms 1624 KB Output is correct
12 Correct 18 ms 1788 KB Output is correct
13 Correct 16 ms 1788 KB Output is correct
14 Correct 18 ms 1856 KB Output is correct
15 Correct 89 ms 3556 KB Output is correct
16 Correct 86 ms 3640 KB Output is correct
17 Correct 85 ms 3584 KB Output is correct
18 Correct 97 ms 3424 KB Output is correct
19 Correct 90 ms 3576 KB Output is correct
20 Correct 101 ms 3820 KB Output is correct
21 Correct 96 ms 3860 KB Output is correct
22 Correct 93 ms 3776 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 0 ms 600 KB Output is correct
3 Correct 1 ms 856 KB Output is correct
4 Correct 0 ms 856 KB Output is correct
5 Correct 1 ms 856 KB Output is correct
6 Correct 1 ms 856 KB Output is correct
7 Correct 3 ms 1112 KB Output is correct
8 Correct 7 ms 1368 KB Output is correct
9 Correct 18 ms 1784 KB Output is correct
10 Correct 1 ms 856 KB Output is correct
11 Correct 11 ms 1624 KB Output is correct
12 Correct 18 ms 1788 KB Output is correct
13 Correct 16 ms 1788 KB Output is correct
14 Correct 18 ms 1856 KB Output is correct
15 Correct 89 ms 3556 KB Output is correct
16 Correct 86 ms 3640 KB Output is correct
17 Correct 85 ms 3584 KB Output is correct
18 Correct 97 ms 3424 KB Output is correct
19 Correct 90 ms 3576 KB Output is correct
20 Correct 101 ms 3820 KB Output is correct
21 Correct 96 ms 3860 KB Output is correct
22 Correct 93 ms 3776 KB Output is correct
23 Incorrect 95 ms 3636 KB Wrong Answer [2]
24 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 0 ms 600 KB Output is correct
3 Correct 1 ms 856 KB Output is correct
4 Correct 0 ms 856 KB Output is correct
5 Correct 1 ms 856 KB Output is correct
6 Correct 1 ms 856 KB Output is correct
7 Correct 3 ms 1112 KB Output is correct
8 Correct 7 ms 1368 KB Output is correct
9 Correct 18 ms 1784 KB Output is correct
10 Correct 1 ms 856 KB Output is correct
11 Correct 11 ms 1624 KB Output is correct
12 Correct 18 ms 1788 KB Output is correct
13 Correct 16 ms 1788 KB Output is correct
14 Correct 18 ms 1856 KB Output is correct
15 Correct 89 ms 3556 KB Output is correct
16 Correct 86 ms 3640 KB Output is correct
17 Correct 85 ms 3584 KB Output is correct
18 Correct 97 ms 3424 KB Output is correct
19 Correct 90 ms 3576 KB Output is correct
20 Correct 101 ms 3820 KB Output is correct
21 Correct 96 ms 3860 KB Output is correct
22 Correct 93 ms 3776 KB Output is correct
23 Incorrect 95 ms 3636 KB Wrong Answer [2]
24 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 0 ms 600 KB Output is correct
3 Correct 1 ms 856 KB Output is correct
4 Correct 0 ms 856 KB Output is correct
5 Correct 1 ms 856 KB Output is correct
6 Correct 1 ms 856 KB Output is correct
7 Correct 3 ms 1112 KB Output is correct
8 Correct 7 ms 1368 KB Output is correct
9 Correct 18 ms 1784 KB Output is correct
10 Correct 1 ms 856 KB Output is correct
11 Correct 11 ms 1624 KB Output is correct
12 Correct 18 ms 1788 KB Output is correct
13 Correct 16 ms 1788 KB Output is correct
14 Correct 18 ms 1856 KB Output is correct
15 Correct 89 ms 3556 KB Output is correct
16 Correct 86 ms 3640 KB Output is correct
17 Correct 85 ms 3584 KB Output is correct
18 Correct 97 ms 3424 KB Output is correct
19 Correct 90 ms 3576 KB Output is correct
20 Correct 101 ms 3820 KB Output is correct
21 Correct 96 ms 3860 KB Output is correct
22 Correct 93 ms 3776 KB Output is correct
23 Incorrect 95 ms 3636 KB Wrong Answer [2]
24 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 0 ms 600 KB Output is correct
3 Correct 1 ms 856 KB Output is correct
4 Correct 0 ms 856 KB Output is correct
5 Correct 1 ms 856 KB Output is correct
6 Correct 1 ms 856 KB Output is correct
7 Correct 3 ms 1112 KB Output is correct
8 Correct 7 ms 1368 KB Output is correct
9 Correct 18 ms 1784 KB Output is correct
10 Correct 1 ms 856 KB Output is correct
11 Correct 11 ms 1624 KB Output is correct
12 Correct 18 ms 1788 KB Output is correct
13 Correct 16 ms 1788 KB Output is correct
14 Correct 18 ms 1856 KB Output is correct
15 Correct 89 ms 3556 KB Output is correct
16 Correct 86 ms 3640 KB Output is correct
17 Correct 85 ms 3584 KB Output is correct
18 Correct 97 ms 3424 KB Output is correct
19 Correct 90 ms 3576 KB Output is correct
20 Correct 101 ms 3820 KB Output is correct
21 Correct 96 ms 3860 KB Output is correct
22 Correct 93 ms 3776 KB Output is correct
23 Incorrect 95 ms 3636 KB Wrong Answer [2]
24 Halted 0 ms 0 KB -