oj.uz

Submission #477664

# Submission time Handle Problem Language Result Execution time Memory
477664 2021-10-03T02:11:05 Z HappyPacMan Minerals (JOI19_minerals) C++14
40 / 100
 58 ms 6564 KB 
#include "minerals.h"
#include <bits/stdc++.h>
using namespace std;

int curr = 0;

bool change(int u){
    int nxt = Query(u);
    bool res = (nxt != curr);
    curr = nxt;
    return res;
}

void Solve(int N){
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    vector<int> group[2];
    for(int i=1;i<=2*N;i++) group[change(i)].emplace_back(i);
    shuffle(group[0].begin(),group[0].end(),rng);
    int l[N],r[N];
    vector<int> mid[N];
    for(int i=0;i<N;i++){
        l[i] = 0;
        r[i] = N-1;
        mid[r[i] - (382*(r[i]-l[i]+1)/1000)].emplace_back(i);
    }
    // for(auto u : group[0]) cout << u << ' '; cout << '\n';
    // for(auto u : group[1]) cout << u << ' '; cout << '\n';
    int found = 0;
    while(found < N){
        // for(int i=0;i<N;i++) cout << l[i] << ' '; cout << '\n';
        // for(int i=0;i<N;i++) cout << r[i] << ' '; cout << '\n'; cout << '\n';
        int prefix[N];
        memset(prefix,0,sizeof(prefix));
        for(int i=0;i<N;i++){
            if(l[i] != r[i]){
                prefix[l[i]]++;
                if(r[i]+1 < N) prefix[r[i]+1]--;
            }
        }
        for(int i=1;i<N;i++) prefix[i] += prefix[i-1];
        for(int i=N-1;i>=0;i--){
            if(!prefix[i]) continue;
            change(group[0][i]);
            vector<int> curr = mid[i];
            mid[i].clear();
            for(auto u : curr){
                bool nxt = change(group[1][u]);
                if(nxt){
                    l[u] = i;
                    int nxm = l[u] + (618*(r[u]-l[u]+1)/1000);
                    if(nxm == r[u]) nxm--;
                    // cout << "nxm 1 : " << group[0][i] << ' ' << group[1][u] << ' ' << nxm << ' ' << r[u] << ' ' << l[u] << '\n';
                    if(l[u] == r[u]){
                        Answer(group[0][l[u]],group[1][u]);
                        found++;
                    }else mid[nxm].emplace_back(u);
                }else{
                    r[u] = i-1;
                    int nxm = r[u] - (382*(r[u]-l[u]+1)/1000);
                    // cout << "nxm 2 : " << group[0][i] << ' ' << group[1][u] << ' ' << nxm << ' ' << r[u] << ' ' << l[u] << '\n';
                    if(l[u] == r[u]){
                        Answer(group[0][l[u]],group[1][u]);
                        found++;
                    }else mid[nxm].emplace_back(u);
                }
            }
        }
        memset(prefix,0,sizeof(prefix));
        for(int i=0;i<N;i++){
            if(l[i] != r[i]){
                prefix[l[i]]++;
                if(r[i]+1 < N) prefix[r[i]+1]--;
            }
        }
        for(int i=1;i<N;i++) prefix[i] += prefix[i-1];
        for(int i=0;i<N;i++){
            if(!prefix[i]) continue;
            change(group[0][i]);
            vector<int> curr = mid[i];
            mid[i].clear();
            for(auto u : curr){
                bool nxt = change(group[1][u]);
                if(nxt){
                    l[u] = i+1;
                    int nxm = l[u] + (382*(r[u]-l[u]+1)/1000);
                    // cout << "nxm 3 : " << group[0][i] << ' ' << group[1][u] << ' ' << nxm << ' ' << r[u] << ' ' << l[u] << '\n';
                    if(l[u] == r[u]){
                        Answer(group[0][l[u]],group[1][u]);
                        found++;
                    }else mid[nxm].emplace_back(u);
                }else{
                    r[u] = i;
                    int nxm = r[u] - (618*(r[u]-l[u]+1)/1000);
                    if(nxm == l[u]) nxm++;
                    // cout << "nxm 4 : " << group[0][i] << ' ' << group[1][u] << ' ' << nxm << ' ' << r[u] << ' ' << l[u] << '\n';
                    if(l[u] == r[u]){
                        Answer(group[0][l[u]],group[1][u]);
                        found++;
                    }else mid[nxm].emplace_back(u);
                }
            }
        }
    }
}

Subtask #1
6.0 / 6.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 3 ms 556 KB Output is correct
3 Correct 5 ms 884 KB Output is correct
4 Correct 11 ms 1528 KB Output is correct
5 Correct 22 ms 2668 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 0 ms 200 KB Output is correct
4 Correct 0 ms 200 KB Output is correct
5 Correct 1 ms 328 KB Output is correct
6 Correct 3 ms 556 KB Output is correct
7 Correct 5 ms 884 KB Output is correct
8 Correct 11 ms 1528 KB Output is correct
9 Correct 22 ms 2668 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 15 ms 1848 KB Output is correct
12 Correct 22 ms 2752 KB Output is correct
13 Correct 24 ms 2680 KB Output is correct
14 Correct 22 ms 2676 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 0 ms 200 KB Output is correct
4 Correct 0 ms 200 KB Output is correct
5 Correct 1 ms 328 KB Output is correct
6 Correct 3 ms 556 KB Output is correct
7 Correct 5 ms 884 KB Output is correct
8 Correct 11 ms 1528 KB Output is correct
9 Correct 22 ms 2668 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 15 ms 1848 KB Output is correct
12 Correct 22 ms 2752 KB Output is correct
13 Correct 24 ms 2680 KB Output is correct
14 Correct 22 ms 2676 KB Output is correct
15 Incorrect 58 ms 6564 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 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 0 ms 200 KB Output is correct
4 Correct 0 ms 200 KB Output is correct
5 Correct 1 ms 328 KB Output is correct
6 Correct 3 ms 556 KB Output is correct
7 Correct 5 ms 884 KB Output is correct
8 Correct 11 ms 1528 KB Output is correct
9 Correct 22 ms 2668 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 15 ms 1848 KB Output is correct
12 Correct 22 ms 2752 KB Output is correct
13 Correct 24 ms 2680 KB Output is correct
14 Correct 22 ms 2676 KB Output is correct
15 Incorrect 58 ms 6564 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 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 0 ms 200 KB Output is correct
4 Correct 0 ms 200 KB Output is correct
5 Correct 1 ms 328 KB Output is correct
6 Correct 3 ms 556 KB Output is correct
7 Correct 5 ms 884 KB Output is correct
8 Correct 11 ms 1528 KB Output is correct
9 Correct 22 ms 2668 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 15 ms 1848 KB Output is correct
12 Correct 22 ms 2752 KB Output is correct
13 Correct 24 ms 2680 KB Output is correct
14 Correct 22 ms 2676 KB Output is correct
15 Incorrect 58 ms 6564 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 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 0 ms 200 KB Output is correct
4 Correct 0 ms 200 KB Output is correct
5 Correct 1 ms 328 KB Output is correct
6 Correct 3 ms 556 KB Output is correct
7 Correct 5 ms 884 KB Output is correct
8 Correct 11 ms 1528 KB Output is correct
9 Correct 22 ms 2668 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 15 ms 1848 KB Output is correct
12 Correct 22 ms 2752 KB Output is correct
13 Correct 24 ms 2680 KB Output is correct
14 Correct 22 ms 2676 KB Output is correct
15 Incorrect 58 ms 6564 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 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 0 ms 200 KB Output is correct
4 Correct 0 ms 200 KB Output is correct
5 Correct 1 ms 328 KB Output is correct
6 Correct 3 ms 556 KB Output is correct
7 Correct 5 ms 884 KB Output is correct
8 Correct 11 ms 1528 KB Output is correct
9 Correct 22 ms 2668 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 15 ms 1848 KB Output is correct
12 Correct 22 ms 2752 KB Output is correct
13 Correct 24 ms 2680 KB Output is correct
14 Correct 22 ms 2676 KB Output is correct
15 Incorrect 58 ms 6564 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 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 0 ms 200 KB Output is correct
4 Correct 0 ms 200 KB Output is correct
5 Correct 1 ms 328 KB Output is correct
6 Correct 3 ms 556 KB Output is correct
7 Correct 5 ms 884 KB Output is correct
8 Correct 11 ms 1528 KB Output is correct
9 Correct 22 ms 2668 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 15 ms 1848 KB Output is correct
12 Correct 22 ms 2752 KB Output is correct
13 Correct 24 ms 2680 KB Output is correct
14 Correct 22 ms 2676 KB Output is correct
15 Incorrect 58 ms 6564 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -