Submission #997390

#	Time	Username	Problem	Language	Result	Execution time	Memory
997390		12345678	Minerals (JOI19_minerals)	C++17	75 / 100	113 ms	3056 KiB

minerals

#include "minerals.h"
#include <bits/stdc++.h>

using namespace std;

const int nx=5e4+5;

mt19937 rng(time(0));

int p, c;
vector<int> l, r;


int update(int x)
{
    p=Query(x);
    swap(c, p);
    return c!=p;
}

vector<int> shuffle(vector<int> &x)
{
    vector<pair<int, int>> tmp;
    vector<int> res(x.size());
    for (int i=0; i<x.size(); i++) tmp.push_back({rng(), i});
    sort(tmp.begin(), tmp.end());
    for (int i=0; i<x.size(); i++) res[i]=x[tmp[i].second];
    return res;
}

void solve(vector<int> &l, vector<int> &r, int t)
{
    int sz=l.size();
    if (sz==1) return Answer(l[0], r[0]), void();
    l=shuffle(l);
    r=shuffle(r);
    int md=(sz-1)/2;
    vector<int> l1, l2, r1, r2;
    for (int i=0; i<=md; i++) l1.push_back(l[i]), update(l[i]);
    for (int i=md+1; i<sz; i++) r1.push_back(l[i]);
    for (int i=0; i<sz; i++)
    {
        if (l2.size()==sz) r2.push_back(r[i]);
        else if (r2.size()==sz) l2.push_back(r[i]);
        else if (update(r[i])==t) l2.push_back(r[i]);
        else r2.push_back(r[i]); 
    }
    solve(l1, l2, !t); solve(r1, r2, t);
}

void Solve(int N) {
    for (int i=1; i<=2*N; i++) 
    {
        if (update(i)) l.push_back(i);
        else r.push_back(i);
    }
    solve(l, r, 1);
}

/*
5
4 7
1 2
8 3
6 10
9 5
*/

Compilation message (stderr)

minerals.cpp: In function 'std::vector<int> shuffle(std::vector<int>&)':
minerals.cpp:25:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     for (int i=0; i<x.size(); i++) tmp.push_back({rng(), i});
      |                   ~^~~~~~~~~
minerals.cpp:27:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     for (int i=0; i<x.size(); i++) res[i]=x[tmp[i].second];
      |                   ~^~~~~~~~~
minerals.cpp: In function 'void solve(std::vector<int>&, std::vector<int>&, int)':
minerals.cpp:43:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   43 |         if (l2.size()==sz) r2.push_back(r[i]);
      |             ~~~~~~~~~^~~~
minerals.cpp:44:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   44 |         else if (r2.size()==sz) l2.push_back(r[i]);
      |                  ~~~~~~~~~^~~~

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