#1160737 (C++17) No.3591 I Love Graph

• 問題: No.3591 I Love Graph
• ユーザー: trqs
• 提出日時: 2026-04-20 09:39:26
• 言語: C++17 (gcc 15.2.0 + boost 1.90.0)
• 結果: AC
• 実行時間: 170 ms / 2,000 ms
• コード長: 3,695 bytes
• コンパイル時間: 1,303 ms
• コンパイル使用メモリ: 218,396 KB
• 実行使用メモリ: 5,888 KB
• 平均クエリ数: 2887.28
• 最終ジャッジ日時: 2026-07-17 20:52:50
• 合計ジャッジ時間: 5,319 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge3_0

ファイルパターン	結果
other	AC * 36

コンパイルメッセージ

In file included from /home/linuxbrew/.linuxbrew/Cellar/gcc@15/15.3.0/include/c++/15/x86_64-pc-linux-gnu/bits/c++allocator.h:33,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc@15/15.3.0/include/c++/15/bits/allocator.h:46,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc@15/15.3.0/include/c++/15/string:45,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc@15/15.3.0/include/c++/15/bitset:54,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc@15/15.3.0/include/c++/15/x86_64-pc-linux-gnu/bits/stdc++.h:54,
                 from main.cpp:1:
In member function 'void std::__new_allocator<_Tp>::deallocate(_Tp*, size_type) [with _Tp = int]',
    inlined from 'static void std::allocator_traits<std::allocator<_CharT> >::deallocate(allocator_type&, pointer, size_type) [with _Tp = int]' at /home/linuxbrew/.linuxbrew/Cellar/gcc@15/15.3.0/include/c++/15/bits/alloc_traits.h:649:23,
    inlined from 'void std::_Vector_base<_Tp, _Alloc>::_M_deallocate(pointer, std::size_t) [with _Tp = int; _Alloc = std::allocator<int>]' at /home/linuxbrew/.linuxbrew/Cellar/gcc@15/15.3.0/include/c++/15/bits/stl_vector.h:396:19,
    inlined from 'void std::_Vector_base<_Tp, _Alloc>::_M_deallocate(pointer, std::size_t) [with _Tp = int; _Alloc = std::allocator<int>]' at /home/linuxbrew/.linuxbrew/Cellar/gcc@15/15.3.0/include/c++/15/bits/stl_vector.h:392:7,
    inlined from 'std::_Vector_base<_Tp, _Alloc>::~_Vector_base() [with _Tp = int; _Alloc = std::allocator<int>]' at /home/linuxbrew/.linuxbrew/Cellar/gcc@15/15.3.0/include/c++/15/bits/stl_vector.h:375:15,
    inlined from 'std::vector<_Tp, _Alloc>::~vector() [with _Tp = int; _Alloc = std::allocator<int>]' at /home/linuxbrew/.linuxbrew/Cellar/gcc@15/15.3.0/include/c++/15/bits/stl_vector.h:805:7,
    inlined from 'int main()' at main.cpp:147:24:
/home/linuxbrew/.linuxbrew/Cellar/gcc@15/15.3.0/include/c++/15/bits/new_allocator.h:172:66: warning: 'void operator delete(void*, std::size_t)' called on pointer '<unkno

ソースコード

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 1e9 + 7;
const int N = 200005;
const int INF = 0x3f3f3f3f;
namespace FastIO {
const int SIZ = 1 << 20;
char ibuf[SIZ], *iS, *iT;
char obuf[SIZ], *oS = obuf, *oT = obuf + SIZ - 1;
inline char getch() {
    return (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZ, stdin), (iS == iT ? EOF : *iS++)) : *iS++);
}
template <typename T>
inline void read(T& x) {
    char c = getch();
    x = 0;
    bool f = 0;
    while (!isdigit(c)) {
        if (c == '-') f = 1;
        c = getch();
    }
    while (isdigit(c)) {
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getch();
    }
    if (f) x = -x;
}
inline void read(char& c) {
    while ((c = getch()) <= 32);
}
inline void read(char* s) {
    char c = getch();
    while (c <= 32) c = getch();
    while (c > 32) {
        *s++ = c;
        c = getch();
    }
    *s = '\0';
}
inline void read(string& s) {
    s.clear();
    char c = getch();
    while (c <= 32) c = getch();
    while (c > 32) {
        s += c;
        c = getch();
    }
}
inline void flush() {
    fwrite(obuf, 1, oS - obuf, stdout);
    oS = obuf;
}
inline void putch(char x) {
    *oS++ = x;
    if (oS == oT) flush();
}
template <typename T>
inline void write(T x) {
    if (x < 0) {
        putch('-');
        x = -x;
    }
    if (x > 9) write(x / 10);
    putch(x % 10 + 48);
}
inline void write(const char* s) {
    while (*s) putch(*s++);
}
inline void write(const string& s) {
    for (char c : s) putch(c);
}
struct IO {
    ~IO() {
        flush();
    }
    template <typename T>
    IO& operator>>(T& x) {
        read(x);
        return *this;
    }
    template <typename T>
    IO& operator<<(const T& x) {
        write(x);
        return *this;
    }
} io;
}  // namespace FastIO
using namespace FastIO;
using i128 = __int128;
using u128 = __uint128_t;
using ull = unsigned long long;
template <typename T>
constexpr std::make_unsigned_t<T> gcd(T a, T b) {
    using U = std::make_unsigned_t<T>;
    U m = a < 0 ? U(-a) : U(a);
    U n = b < 0 ? U(-b) : U(b);
    if (m == 0) return n;
    if (n == 0) return m;
    int i = __builtin_ctz(m);
    m >>= i;
    int j = __builtin_ctz(n);
    n >>= j;
    int k = min(i, j);
    while (true) {
        if (m > n) swap(m, n);
        n -= m;
        if (n == 0) return m << k;
        n >>= __builtin_ctz(n);
    }
}
inline int lg(int __n) {
    return sizeof(int) * __CHAR_BIT__ - 1 - __builtin_clz(__n);
}
ll powmod(ll x, ll y, ll m = mod) {
    ll res = 1;
    while (y) {
        if (y & 1) res = res * x % m;
        y >>= 1;
        x = x * x % m;
    }
    return res;
}
int ask(int u, vector<int> S) {
    if (S.empty()) return 0;
    cout << "? 1 " << S.size() << " " << u;
    for (int v : S) cout << " " << v;
    cout << "\n";
    cout.flush();
    int res;
    cin >> res;
    return res;
}
int main() {
    int n;
    cin >> n;
    vector<pair<int, int>> e;
    for (int u = 1; u < n; u++) {
        vector<int> S;
        for (int v = u + 1; v <= n; v++) S.push_back(v);
        while (!S.empty()) {
            if (!ask(u, S)) break;
            int L = 0, R = S.size() - 1;
            while (L < R) {
                int mid = (L + R) >> 1;
                vector<int> lh(S.begin() + L, S.begin() + mid + 1);
                if (ask(u, lh)) {
                    R = mid;
                } else {
                    L = mid + 1;
                }
            }
            int v = S[L];
            e.push_back({u, v});
            S.erase(S.begin() + L);
        }
    }
    cout << "! " << e.size() << "\n";
    for (auto [u, v] : e) cout << u << " " << v << "\n";
    cout.flush();
    return 0;
}