Submission #378194

#	Time	Username	Problem	Language	Result	Execution time	Memory
378194		casperwang	Minerals (JOI19_minerals)	C++14	85 / 100	65 ms	4332 KiB

minerals

#include "minerals.h"
#include <bits/stdc++.h>
#define All(x) x.begin(), x.end()
#define pb emplace_back
using namespace std;
#define debug(args...) kout("[ " + string(#args) + " ]", args)
void kout() { cerr << endl; }
template <class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ',kout(b...); }
template <class T> void pary(T L, T R) { while (L != R) cerr << *L << " \n"[++L==R]; }
 
const double e = exp(1);
int pre, now;
 
void check(vector <int> A, vector <int> B, bool flagA, bool flagB) {
        if (A.size() == 1) {
                Answer(A[0], B[0]);
                return;
        }
        int len = max<int>(1, B.size() / e);
        vector <int> LA, RA, LB, RB;
        for (int i = 0; i < len; i++) {
                pre = now;
                now = Query(B[i]);
                LB.pb(B[i]);
        }
        for (int i = 0; i < A.size(); i++) {
                pre = now;
                now = Query(A[i]);
                if ( (!flagA && !flagB && now == pre)
                || (!flagA &&  flagB && now == pre+1)
                || ( flagA && !flagB && now == pre)
                        || ( flagA &&  flagB && now == pre-1)) {
                        LA.pb(A[i]);
                } else {
                        RA.pb(A[i]);
                }
        }
        for (int i = len; i < B.size(); i++) {
                RB.pb(B[i]);
        }
        check(LA, LB, !flagA, !flagB);
        check(RA, RB, !flagA, flagB);
}
 
void Solve(int N) {
        // srand(time(NULL));
 
        vector <int> num(2*N);
        for (int i = 0; i < 2*N; i++) num[i] = i+1;
        // random_shuffle(All(num));
 
        vector <int> A, B;
        for (int id : num) {
                pre = now;
                now = Query(id);
                if (now != pre + 1) {
                        B.pb(id);
                } else {
                        A.pb(id);
                }
        }
        check(A, B, true, true);
}

Compilation message (stderr)

minerals.cpp: In function 'void check(std::vector<int>, std::vector<int>, bool, bool)':
minerals.cpp:26:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |         for (int i = 0; i < A.size(); i++) {
      |                         ~~^~~~~~~~~~
minerals.cpp:38:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |         for (int i = len; i < B.size(); i++) {
      |                           ~~^~~~~~~~~~

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