Submission #997631

#	Time	Username	Problem	Language	Result	Execution time	Memory
997631		TimDee	Minerals (JOI19_minerals)	C++17	0 / 100	2 ms	600 KiB

minerals

#include "minerals.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0; i<(n); ++i)
#define pb push_back
#define pi pair<int,int>
#define f first
#define s second 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int query(int x) {
    return Query(x+1);
}
void Solve(int n) {

    vector<int> in(2*n), c(2*n);
    vector<int> f,s;

    int last=0;
    vector<int> p; forn(i,2*n) p.pb(i);
    shuffle(p.begin(),p.end(),rng);
    forn(i,2*n) {
        if (last==n) {
            s.pb(p[i]); continue;
        }
        int z = query(p[i]);
        if (z > last) f.pb(p[i]);
        else s.pb(p[i]); 
        in[p[i]]=1;
        last = z;
    }

    forn(i,n) c[f[i]]=i;

    vector<pi> v(n);
    forn(i,n) v[i]={0,n-1};

    multiset<int> st;
    forn(i,n) st.insert(n/2);

    vector<vector<int>> ok(n);
    forn(i,n) ok[n/2].pb(i);

    set<int> alive;
    forn(i,n) alive.insert(i);

    vector<vector<int>> other(n);

    int dir = -1;
    int pos = n-1;
    int q2=0, q3=0;
    while (st.size()) {
        ++q2;
        //cout<<pos<<' '<<dir<<'\n';
        //for(auto&x:st) cout<<x<<' '; cout<<'\n';
        //for(auto&x:alive) cout<<x<<' '; cout<<'\n';
        //cout<<'\n';
        //cout.flush();

        if (dir == 1) {

            vector<int> lq,rq;
            for(auto&x:ok[pos]) {
                st.erase(st.find(pos));
                int l=v[x].f, r=v[x].s;
                assert(l!=r);
                int m=(l+r+1)>>1;
                if (lq.size() == m-l) {
                    rq.pb(x); continue;
                }
                if (rq.size() == r-m+1) {
                    lq.pb(x); continue;
                }
                int q = query(s[x]); q3++;
                if (q != last) {
                    rq.pb(x);
                } else {
                    lq.pb(x);
                }
                in[s[x]]^=1;
                last = q;
            }
            ok[pos].clear();
            for(auto&x:lq) {
                int l=v[x].f, r=v[x].s;
                int m=(l+r+1)>>1;
                r=m-1;
                v[x] = {l,r};
                if (l==r) {
                    alive.erase(x);
                } else {
                    st.insert(m);
                    ok[m].pb(x);
                }
            }
            for(auto&x:rq) {
                int l=v[x].f, r=v[x].s;
                int m=(l+r+1)>>1;
                l=m;
                v[x] = {l,r};
                if (l==r) {
                    alive.erase(x);
                } else {
                    st.insert(m);
                    ok[m].pb(x);
                }
            }

            auto it = st.lower_bound(pos);
            if (it==st.end()) {
                dir*=-1;
                continue;
            }

            if (alive.count(pos)) last = query(f[pos]);
            ++pos;

        } else {

            auto it3 = st.upper_bound(pos);
            if (it3!=st.end()) {
                auto it2 = alive.upper_bound(pos);
                pos = *it2;
                dir *= -1; continue;
            }

            if (alive.count(pos)) last = query(f[pos]);

            vector<int> lq,rq;
            for(auto&x:ok[pos]) {
                st.erase(st.find(pos));
                int l=v[x].f, r=v[x].s;
                assert(l!=r);
                int m=(l+r+1)>>1;
                if (lq.size() == m-l) {
                    rq.pb(x); continue;
                }
                if (rq.size() == r-m+1) {
                    lq.pb(x); continue;
                }
                int q = query(s[x]); q3++;
                if (q != last) {
                    l = m;
                    rq.pb(x);
                } else {
                    r = m-1;
                    lq.pb(x);
                }
                in[s[x]]^=1;
                last = q;
            }
            ok[pos].clear();
            for(auto&x:lq) {
                int l=v[x].f, r=v[x].s;
                int m=(l+r+1)>>1;
                r=m-1;
                v[x] = {l,r};
                if (l==r) {
                    alive.erase(x);
                } else {
                    st.insert(m);
                    ok[m].pb(x);
                }
            }
            for(auto&x:rq) {
                int l=v[x].f, r=v[x].s;
                int m=(l+r+1)>>1;
                l=m;
                v[x] = {l,r};
                if (l==r) {
                    alive.erase(x);
                } else {
                    st.insert(m);
                    ok[m].pb(x);
                }
            }

            auto it = st.lower_bound(pos);
            if (it == st.begin()) {
                dir *= -1;
                continue;
            }

            --pos;
        }
    }
    //cout<<"? "<<q2<<' '<<q3<<"  ";

    forn(i,n) Answer(s[i]+1,f[v[i].f]+1);

}

Compilation message (stderr)

minerals.cpp: In function 'void Solve(int)':
minerals.cpp:68:31: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   68 |                 if (lq.size() == m-l) {
      |                     ~~~~~~~~~~^~~~~~
minerals.cpp:71:31: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   71 |                 if (rq.size() == r-m+1) {
      |                     ~~~~~~~~~~^~~~~~~~
minerals.cpp:135:31: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  135 |                 if (lq.size() == m-l) {
      |                     ~~~~~~~~~~^~~~~~
minerals.cpp:138:31: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  138 |                 if (rq.size() == r-m+1) {
      |                     ~~~~~~~~~~^~~~~~~~

• Subtask 1: 0 / 6
• Subtask 2: 0 / 25
• Subtask 3: 0 / 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