結果

問題 No.3448 ABBBBBBBBC
コンテスト
ユーザー zawakasu
提出日時 2026-02-20 22:42:11
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
結果
AC  
実行時間 215 ms / 2,000 ms
コード長 4,297 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,558 ms
コンパイル使用メモリ 242,660 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2026-02-20 22:42:17
合計ジャッジ時間 5,489 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 4
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <iomanip>
#include <cassert>
#include <vector>
#include <algorithm>
#include <utility>
#include <numeric>
#include <tuple>
#include <ranges>
#include <random>
// #include "Src/Number/IntegerDivision.hpp"
// #include "Src/Utility/BinarySearch.hpp"
// #include "Src/Sequence/CompressedSequence.hpp"
// #include "Src/Sequence/RunLengthEncoding.hpp"
// #include "Src/Algebra/Group/AdditiveGroup.hpp"
// #include "Src/DataStructure/FenwickTree/FenwickTree.hpp"
// #include "Src/DataStructure/SegmentTree/SegmentTree.hpp"
// #include "Src/DataStructure/DisjointSetUnion/DisjointSetUnion.hpp"
// #include "Src/DataStructure/Heap/BinaryHeap.hpp"
namespace zawa {}
using namespace zawa;
// #include "atcoder/modint"
// using mint = atcoder::modint998244353;
// #include <array>
// #include <bit>
// #include <bitset>
// #include <climits>
// #include <cmath>
// #include <set>
// #include <unordered_set>
// #include <map>
// #include <unordered_map>
// #include <optional>
// #include <queue>
// #include <stack>
// #include <deque>
// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
using namespace std;
template <class T, class U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
    os << '(' << p.first << ',' << p.second << ')';
    return os;
}
template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
    for (int i = 0 ; i < ssize(v) ; i++)
        os << v[i] << (i + 1 == ssize(v) ? "" : " ");
    return os;
}
vector<long long> solve(long long N, long long K) {
    vector<long long> cnt(10);
    for (int i = 1 ; i < 10 ; i++)
        for (int j = 0 ; j < 10 ; j++)
            for (int k = 0 ; k < 10 ; k++)
                if (i != j and j != k and i != k)
                    cnt[i] += N;
    int head = 1;
    while (cnt[head] < K) {
        K -= cnt[head];
        head++;
    }
    assert(head < 10);
    int sec = 0;
    while (true) {
        if (head == sec) {
            sec++;
            continue;
        }
        if (8LL * N < K) {
            K -= 8 * N;
            sec++;
        }
        else
            break;
    }
    vector<int> low, up;
    for (int i = 0 ; i < 10 ; i++)
        if (head != i and sec != i) 
            (i < sec ? low : up).push_back(i);
    if (K <= N * ssize(low)) {
        assert(low.size());
        long long len = (K + ssize(low) - 1) / ssize(low);
        assert(len >= 1);
        K -= (len - 1) * ssize(low);
        assert(K <= ssize(low));
        return vector<long long>{len+2,head,sec,low[K - 1]};
    }
    K -= N * ssize(low);
    assert(up.size());
    long long len = N - (K - 1) / ssize(up);
    K -= (K - 1) / ssize(up) * ssize(up);
    assert(K <= ssize(up));
    return vector<long long>{len+2,head,sec,up[K - 1]};
}
vector<long long> naive(long long N, long long K) {
    vector<string> cur;
    for (int head = 1 ; head < 10 ; head++)
        for (int mid = 0 ; mid < 10 ; mid++)
            for (int tail = 0 ; tail < 10 ; tail++)
                if (head != mid and mid != tail and tail != head)
                    for (int len = 1 ; len <= N ; len++)
                        cur.push_back(string(1,head+'0')+string(len,mid+'0')+string(1,tail+'0'));
    ranges::sort(cur);
    string ans = cur[K - 1];
    // for (auto a : cur)
    //     cout << a << endl;
    return vector<long long>{ssize(ans),ans[0]-'0',ans[1]-'0',ans.back()-'0'};
    // return vector<long long>{ans[0]-'0',ans[1]-'0'};
}
int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    cout << fixed << setprecision(20);
#if !defined DEBUG
    int T;
    cin >> T;
    while (T--) {
        long long N, K;
        cin >> N >> K;
        cout << solve(N,K) << '\n';
        // cout << naive(N,K) << endl;
    }
#else
    mt19937_64 mt{random_device{}()};
    for (int testcase = 0 ; ; ) {
        cerr << "----------" << ++testcase << "----------" << endl;
        int N = mt() % 50 + 1;
        int K = mt() % (648 * N) + 1;
        auto a = solve(N,K), b = naive(N,K);
        if (a != b) {
            // print testcase
            cout << 1 << endl;
            cout << N << ' ' << K << endl;
            cerr << "you: " << a << endl;
            cout << "correct: " << b << endl;
            exit(0);
        }
    }
#endif
}
0