oj.uz

답안 #1048893

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1048893 2024-08-08T10:28:17 Z GrindMachine Minerals (JOI19_minerals) C++17
100 / 100
 116 ms 4108 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);
        }
    }

    go(v1,v2,1);

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

Subtask #1
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 856 KB Output is correct
2 Correct 0 ms 856 KB Output is correct
3 Correct 0 ms 856 KB Output is correct
4 Correct 0 ms 856 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 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 19 ms 1880 KB Output is correct

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 856 KB Output is correct
2 Correct 0 ms 856 KB Output is correct
3 Correct 0 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 19 ms 1880 KB Output is correct
10 Correct 1 ms 856 KB Output is correct
11 Correct 10 ms 1728 KB Output is correct
12 Correct 18 ms 2048 KB Output is correct
13 Correct 16 ms 1880 KB Output is correct
14 Correct 17 ms 1880 KB Output is correct

Subtask #4
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 856 KB Output is correct
2 Correct 0 ms 856 KB Output is correct
3 Correct 0 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 19 ms 1880 KB Output is correct
10 Correct 1 ms 856 KB Output is correct
11 Correct 10 ms 1728 KB Output is correct
12 Correct 18 ms 2048 KB Output is correct
13 Correct 16 ms 1880 KB Output is correct
14 Correct 17 ms 1880 KB Output is correct
15 Correct 86 ms 3900 KB Output is correct
16 Correct 87 ms 3900 KB Output is correct
17 Correct 82 ms 3684 KB Output is correct
18 Correct 93 ms 3528 KB Output is correct

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 856 KB Output is correct
2 Correct 0 ms 856 KB Output is correct
3 Correct 0 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 19 ms 1880 KB Output is correct
10 Correct 1 ms 856 KB Output is correct
11 Correct 10 ms 1728 KB Output is correct
12 Correct 18 ms 2048 KB Output is correct
13 Correct 16 ms 1880 KB Output is correct
14 Correct 17 ms 1880 KB Output is correct
15 Correct 86 ms 3900 KB Output is correct
16 Correct 87 ms 3900 KB Output is correct
17 Correct 82 ms 3684 KB Output is correct
18 Correct 93 ms 3528 KB Output is correct
19 Correct 94 ms 3896 KB Output is correct
20 Correct 93 ms 3836 KB Output is correct
21 Correct 86 ms 3932 KB Output is correct
22 Correct 86 ms 3412 KB Output is correct

Subtask #6
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 856 KB Output is correct
2 Correct 0 ms 856 KB Output is correct
3 Correct 0 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 19 ms 1880 KB Output is correct
10 Correct 1 ms 856 KB Output is correct
11 Correct 10 ms 1728 KB Output is correct
12 Correct 18 ms 2048 KB Output is correct
13 Correct 16 ms 1880 KB Output is correct
14 Correct 17 ms 1880 KB Output is correct
15 Correct 86 ms 3900 KB Output is correct
16 Correct 87 ms 3900 KB Output is correct
17 Correct 82 ms 3684 KB Output is correct
18 Correct 93 ms 3528 KB Output is correct
19 Correct 94 ms 3896 KB Output is correct
20 Correct 93 ms 3836 KB Output is correct
21 Correct 86 ms 3932 KB Output is correct
22 Correct 86 ms 3412 KB Output is correct
23 Correct 96 ms 3824 KB Output is correct
24 Correct 99 ms 4080 KB Output is correct
25 Correct 90 ms 3676 KB Output is correct
26 Correct 90 ms 3836 KB Output is correct

Subtask #7
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 856 KB Output is correct
2 Correct 0 ms 856 KB Output is correct
3 Correct 0 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 19 ms 1880 KB Output is correct
10 Correct 1 ms 856 KB Output is correct
11 Correct 10 ms 1728 KB Output is correct
12 Correct 18 ms 2048 KB Output is correct
13 Correct 16 ms 1880 KB Output is correct
14 Correct 17 ms 1880 KB Output is correct
15 Correct 86 ms 3900 KB Output is correct
16 Correct 87 ms 3900 KB Output is correct
17 Correct 82 ms 3684 KB Output is correct
18 Correct 93 ms 3528 KB Output is correct
19 Correct 94 ms 3896 KB Output is correct
20 Correct 93 ms 3836 KB Output is correct
21 Correct 86 ms 3932 KB Output is correct
22 Correct 86 ms 3412 KB Output is correct
23 Correct 96 ms 3824 KB Output is correct
24 Correct 99 ms 4080 KB Output is correct
25 Correct 90 ms 3676 KB Output is correct
26 Correct 90 ms 3836 KB Output is correct
27 Correct 99 ms 3716 KB Output is correct
28 Correct 99 ms 3760 KB Output is correct
29 Correct 96 ms 3624 KB Output is correct
30 Correct 99 ms 3652 KB Output is correct

Subtask #8
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 856 KB Output is correct
2 Correct 0 ms 856 KB Output is correct
3 Correct 0 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 19 ms 1880 KB Output is correct
10 Correct 1 ms 856 KB Output is correct
11 Correct 10 ms 1728 KB Output is correct
12 Correct 18 ms 2048 KB Output is correct
13 Correct 16 ms 1880 KB Output is correct
14 Correct 17 ms 1880 KB Output is correct
15 Correct 86 ms 3900 KB Output is correct
16 Correct 87 ms 3900 KB Output is correct
17 Correct 82 ms 3684 KB Output is correct
18 Correct 93 ms 3528 KB Output is correct
19 Correct 94 ms 3896 KB Output is correct
20 Correct 93 ms 3836 KB Output is correct
21 Correct 86 ms 3932 KB Output is correct
22 Correct 86 ms 3412 KB Output is correct
23 Correct 96 ms 3824 KB Output is correct
24 Correct 99 ms 4080 KB Output is correct
25 Correct 90 ms 3676 KB Output is correct
26 Correct 90 ms 3836 KB Output is correct
27 Correct 99 ms 3716 KB Output is correct
28 Correct 99 ms 3760 KB Output is correct
29 Correct 96 ms 3624 KB Output is correct
30 Correct 99 ms 3652 KB Output is correct
31 Correct 104 ms 4108 KB Output is correct
32 Correct 116 ms 3764 KB Output is correct
33 Correct 104 ms 3880 KB Output is correct
34 Correct 99 ms 3608 KB Output is correct

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 856 KB Output is correct
2 Correct 0 ms 856 KB Output is correct
3 Correct 0 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 19 ms 1880 KB Output is correct
10 Correct 1 ms 856 KB Output is correct
11 Correct 10 ms 1728 KB Output is correct
12 Correct 18 ms 2048 KB Output is correct
13 Correct 16 ms 1880 KB Output is correct
14 Correct 17 ms 1880 KB Output is correct
15 Correct 86 ms 3900 KB Output is correct
16 Correct 87 ms 3900 KB Output is correct
17 Correct 82 ms 3684 KB Output is correct
18 Correct 93 ms 3528 KB Output is correct
19 Correct 94 ms 3896 KB Output is correct
20 Correct 93 ms 3836 KB Output is correct
21 Correct 86 ms 3932 KB Output is correct
22 Correct 86 ms 3412 KB Output is correct
23 Correct 96 ms 3824 KB Output is correct
24 Correct 99 ms 4080 KB Output is correct
25 Correct 90 ms 3676 KB Output is correct
26 Correct 90 ms 3836 KB Output is correct
27 Correct 99 ms 3716 KB Output is correct
28 Correct 99 ms 3760 KB Output is correct
29 Correct 96 ms 3624 KB Output is correct
30 Correct 99 ms 3652 KB Output is correct
31 Correct 104 ms 4108 KB Output is correct
32 Correct 116 ms 3764 KB Output is correct
33 Correct 104 ms 3880 KB Output is correct
34 Correct 99 ms 3608 KB Output is correct
35 Correct 109 ms 3980 KB Output is correct
36 Correct 113 ms 4028 KB Output is correct
37 Correct 103 ms 3728 KB Output is correct
38 Correct 103 ms 3600 KB Output is correct