Submission #469620

#	Time	Username	Problem	Language	Result	Execution time	Memory
469620		aZvezda	Library (JOI18_library)	C++14	100 / 100	629 ms	460 KiB

library

#include <cstdio>
#include <vector>
#include "library.h"

#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#define endl "\n"
typedef long long ll;
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;
#define out(x) "{" << (#x) << ": " << x << "} "

const int MAX_N = 1e3 + 10;
set<int> lft;
bool used[MAX_N];

vector<int> load(int cnt, int n) {
    vector<int> ret(n, 0);
    for(auto it : lft) {
        if(cnt <= 0) {break;}
        cnt --;
        ret[it - 1] = 1;
    }
    return ret;
}

int getm(int m) {
    for(auto it : lft) {
        m --;
        if(m <= 0) {
            return it;
        }
    }
    return -1;
}

void Solve(int n) {
    vector<int> ans;

    lft.clear();

    for(int i = 1; i <= n; i ++) {
        lft.insert(i);
    }

    lft.erase(1);
    vector<int> ret = {1};

    for(int iter = 0; iter < 2; iter ++) {
        while(ret.size() < n) {
            auto curr = ret.back();

            int l = 0, r = lft.size();
            while(l < r - 1) {
                int m = (l + r) / 2ll;

                auto quer = load(m, n);

                auto ans1 = Query(quer);
                quer[curr - 1] = 1;
                auto ans2 = Query(quer);

                if(ans1 < ans2) {
                    l = m;
                } else {
                    r = m;
                }
            }

            auto quer = load(r, n);

            auto ans1 = Query(quer);
            quer[curr - 1] = 1;
            auto ans2 = Query(quer);

            if(ans1 < ans2) {
                break;
            } else {
                int now = getm(r);
                ret.push_back(now);
                lft.erase(now);
            }
        }

        reverse(ret.begin(), ret.end());
    }

    Answer(ret);
}

Compilation message (stderr)

library.cpp: In function 'void Solve(int)':
library.cpp:55:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   55 |         while(ret.size() < n) {
      |               ~~~~~~~~~~~^~~

• Subtask 1: 19 / 19
• Subtask 2: 81 / 81