제출 #1190159

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1190159		Ghulam_Junaid	Minerals (JOI19_minerals)	C++20	컴파일 에러	0 ms	0 KiB

minerals

#include <bits/stdc++.h>
#include "minerals.h"
using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MXN = 1e5 + 100;
int n, lo[MXN], hi[MXN];
vector<int> a, b, vec[MXN];

int get_mid(int l, int r, bool rev){
    int mid;
    if (!rev){
        mid = (618 * l + 382 * r) / 1000;
        if (mid <= l) mid = l + 1;
    }
    else {
        mid = (382 * l + 618 * r + 999) / 1000;
        if (mid >= r) mid = r - 1;
    }
    return mid;
}

void Solve(int nn){
    srand(time(NULL));

    n = nn;

    vector<int> S;
    for (int i = 1; i <= 2 * n; i ++)
        S.push_back(i);
    for (int i = 2 * n; i > 0; i --)
        swap(S[i - 1], S[rng() % i]);

    int D = 0;
    for (int i = 1; i <= 2 * n; i ++){
        if (Query(i) == D){
            b.push_back(i);
        }
        else{
            D++;
            a.push_back(i);
        }
    }

    for (int i : a){
        int lb = lower_bound(b.begin(), b.end(), i) - b.begin();
        lo[i] = lb - 1;
        hi[i] = n - 1;
    }

    for (int i : a){
        if (hi[i] - lo[i] <= 1) continue;
        int mid = get_mid(lo[x], hi[x], 0);
        vec[mid].push_back(i);
    }

    for (int it = 0; it < 16; it ++){        
        if (it % 2 == 1){
            for (int i = 0; i < n; i ++){
                int D = Query(b[i]);
                int tmpD;
                for (int x : vec[i]){
                    tmpD = Query(x);
                    if (tmpD == D)
                        hi[x] = i;
                    else
                        lo[x] = i;
                    D = tmpD;

                    if (hi[x] - lo[x] > 1){
                        int mid = get_mid(lo[x], hi[x], 0);
                        vec[mid].push_back(x);
                    }
                }
                vec[i].clear();
            }
        }
        else{
            int D = n, tmpD;
            for (int i = n - 1; i >= 0; i --){
                for (int x : vec[i]){
                    tmpD = Query(x);
                    if (tmpD == D)
                        hi[x] = i;
                    else
                        lo[x] = i;
                    D = tmpD;

                    if (hi[x] - lo[x] > 1){
                        int mid = get_mid(lo[x], hi[x], 1);
                        vec[mid].push_back(x);
                    }
                }
                vec[i].clear();
                D = Query(b[i]);
            }
        }
    }

    for (int i : a)
        Answer(i, b[hi[i]]);
}

/*

A1. Suffle the slices.
B2. R = cnt-1; ans = cnt;
B3. L = last perfect matching
B4. If group[0].size() == N then rest are group[1]
A5. Find mid only consider non paired items -> use fenwick tree
A6. Ratio = 618 : 382
B7. Iterate back and forth -> reverse ratio
B8. Go back when there is no mid ahead -> use set
A9. Just iterate non paired item -> use fenwick tree
C10. Finish when all answer obtained
A11. Query once

*/

컴파일 시 표준 에러 (stderr) 메시지

minerals.cpp: In function 'void Solve(int)':
minerals.cpp:54:30: error: 'x' was not declared in this scope
   54 |         int mid = get_mid(lo[x], hi[x], 0);
      |                              ^