제출 #469612

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
469612		aZvezda	도서관 (JOI18_library)	C++14	0 / 100	60 ms	296 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;

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

    lft.erase(1);

    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[0] = 1;
        auto ans2 = Query(quer);

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

    int now = getm(r);
    vector<int> ret = {1, now};
    lft.erase(now);

    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());

    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);
        }
    }

    Answer(ret);
}

컴파일 시 표준 에러 (stderr) 메시지

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

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