제출 #145011

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
145011		osaaateiasavtnl	도서관 (JOI18_library)	C++14	19 / 100	3100 ms	18064 KiB

library

#include <bits/stdc++.h>
using namespace std; 
mt19937 rnd(228);
vector <int> ans, pos;
int N;
#ifdef HOME
int Q = 0;
int Query(vector <int> m) { 
    if (m.size() == 1) return 1;
    ++Q;
    vector <bool> used(N);
    for (int i = 0; i < N; ++i) {
        if (m[i]) used[pos[i]] = 1;
    }   
    int ans = 0;
    for (int i = 0; i < N; ++i) {
        ans += used[i] && (!i || !used[i - 1]);
    }   
    return ans;
}
void Answer(vector <int> a) { 
    cout << "Q = " << Q << '\n';
    auto b = a; reverse(b.begin(), b.end());
    if (a == ans || b == ans) cout << "correct\n";
    else {
        for (int e : ans) cout << e << ' '; cout << '\n';
        for (int e : a) cout << e << ' '; cout << '\n';
        cout << "WA\n";
        exit(0);
    }
}
#else
#include "library.h"
#endif

#define ii pair <int, int>
#define app push_back
// Query()
// Answer()
vector <ii> ed;
vector <int> g[1001];
int query(vector<int> v) {
    vector<int> m(N,0);
    for(int i:v) m[i]=1;
    return Query(m);
}
int new_edge(vector <int> v) {
    int ans = v.size() - query(v);
    vector<int> m(N,0);
    for(int i:v) m[i]=1;    
    for (auto e : ed) ans -= m[e.first] && m[e.second];
    return ans; 
}
void add(int u, int v) {
    ed.app({u, v});
    g[u].app(v); g[v].app(u);
}
void rec(vector <int> a) {
    if (a.size() == 2) { add(a[0], a[1]); return; }   
    int m = a.size() >> 1;
    while (1) {     
        shuffle(a.begin(), a.end(), rnd);
        vector <int> l, r;
        for (int i = 0; i < m; ++i) l.app(a[i]);
        for (int i = m; i < a.size(); ++i) r.app(a[i]);
        bool t1 = new_edge(l), t2 = new_edge(r);
        if (!t1 && !t2) continue;
        if (t1) rec(l); if (t2) rec(r);
        break;
    }
}
void Solve(int n) {
    #ifdef HOME
    Q = 0;
    #endif
    N = n;
    for (int i = 0; i < 1001; ++i) g[i].clear();
    ed.clear();
    while (ed.size() < n - 1) {
        vector <int> cur;
        for (int i = 0; i < n; ++i) cur.app(i);
        rec(cur);        
    }
    vector <int> ans;
    for (int i = 0; i < n; ++i) {
        if (g[i].size() != 2) {
            ans.app(i); break;
        }
    }       
    int p = -1;
    for (int i = 0; i < n - 1; ++i) {
        for (int v : g[ans.back()]) {
            if (v != p) {
                p = ans.back();
                ans.app(v);
                break;
            }
        }
    }
    for (auto &e : ans) ++e;
    Answer(ans);
}
#ifdef HOME 
int main() {
    int t = 10;
    while (t--) {
        int N = 1000;
        ans.clear();
        pos.resize(N);
        for (int i = 1; i <= N; ++i) ans.app(i);
        shuffle(ans.begin(), ans.end(), rnd);
        for (int i = 0; i < N; ++i) pos[ans[i] - 1] = i;
        Solve(N);
    }
}
#endif

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

library.cpp: In function 'void rec(std::vector<int>)':
library.cpp:65:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = m; i < a.size(); ++i) r.app(a[i]);
                         ~~^~~~~~~~~~
library.cpp:68:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
         if (t1) rec(l); if (t2) rec(r);
         ^~
library.cpp:68:25: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
         if (t1) rec(l); if (t2) rec(r);
                         ^~
library.cpp: In function 'void Solve(int)':
library.cpp:79:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (ed.size() < n - 1) {
            ~~~~~~~~~~^~~~~~~

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