Submission #501554

#	Time	Username	Problem	Language	Result	Execution time	Memory
501554		hidden1	Minerals (JOI19_minerals)	C++14	40 / 100	47 ms	3984 KiB

minerals

#include "minerals.h"
#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#ifndef LOCAL
#define cerr if(false) cerr
#endif
#define endl "\n"
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x.size())
typedef long long ll;
template<class T, template<class T2, class A=allocator<T2> > class cont> inline ostream &operator <<(ostream &out, const cont<T> &x) { for(const auto &it : x) { out << it << " ";} return out;}
template<class T, template<class T2, class A=allocator<T2> > class cont> inline istream &operator >>(istream &in, cont<T> &x) { for(auto &it : x) { in >> it;} return in;}
template<class T, class T2> inline ostream &operator <<(ostream &out, const pair<T, T2> &x) { out << x.first << " " << x.second; return out;}
template<class T, class T2> inline istream &operator >>(istream &in, pair<T, T2> &x) { in >> x.first >> x.second; return in;}
template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const ll mod = 1e9 + 7;

ll f(int x) {
    if(x == 0) {
        return 0;
    }
    return f(x * 3 / 4) + f(x / 4) + x * 3 / 2;
}

int last = 0;
pair<int, bool> query(int x) {
    int now = Query(x);
    if(last == now) {
        last = now;
        return {last, 0};
    } else {
        last = now;
        return {last, 1};
    }
}

void daq(vector<int> small, vector<int> big, bool on = false) {
    cerr << "Hereeee" << endl;
    for(auto it : small) {
        cerr << it << " ";
    }
    cerr << endl;
    for(auto it : big) {
        cerr << it << " ";
    }
    cerr << endl;

    if(small.size() == 1) {
        Answer(small[0], big[0]);
        return;
    }
    if(small.size() == 0) {
        return;
    }

    int m = max(1, (int)(small.size() * 0.3));
    for(int i = 0; i < m; i ++) {
        query(small[i]);
    }
    vector<int> ll, lr, rl, rr;
    for(int i = 0; i < m; i ++) {
        ll.push_back(small[i]);
    }
    for(int i = m; i < small.size(); i ++) {
        rl.push_back(small[i]);
    }

    for(auto it : big) {
        if(!query(it).second ^ on) {
            lr.push_back(it);
        } else {
            rr.push_back(it);
        }
    }

    daq(ll, lr, !on);
    daq(rl, rr, on);

}

void Solve(int n) {
    vector<int> l, r;
    for(int i = 1; i <= 2 * n; i ++) {
        if(query(i).second) {
            l.push_back(i);
        } else {
            r.push_back(i);
        }
    }
    random_shuffle(l.begin(), l.end());
    random_shuffle(r.begin(), r.end());
    for(int i = 1; i <= 2 * n; i ++) {
        query(i);
    }
    daq(l, r, false);
}
/*
4
1 5
2 6
3 4
7 8
*/

Compilation message (stderr)

minerals.cpp: In function 'void daq(std::vector<int>, std::vector<int>, bool)':
minerals.cpp:67:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |     for(int i = m; i < small.size(); i ++) {
      |                    ~~^~~~~~~~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 25 / 25
• Subtask 3: 9 / 9
• Subtask 4: 0 / 30
• Subtask 5: 0 / 5
• Subtask 6: 0 / 5
• Subtask 7: 0 / 5
• Subtask 8: 0 / 5
• Subtask 9: 0 / 10