QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#711575#7949. K-Lotterykizen#RE 0ms3596kbC++204.2kb2024-11-05 12:10:142024-11-05 12:10:15

Judging History

你现在查看的是最新测评结果

  • [2024-11-05 12:10:15]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:3596kb
  • [2024-11-05 12:10:14]
  • 提交

answer

#include <bits/stdc++.h>

#ifndef LOCAL
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#endif

#define sz(v) ((int)v.size())
#define all(v) v.begin(), v.end()
#define pb push_back
#define pi array<int, 2>
// #define comp(v) (sort(all(v)), v.erase(unique(all(v)), v.end()))
#define lb(v, x) (lower_bound(all(v), x) - v.begin())

using namespace std;

#define int long long

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int k, m, n; cin >> k >> m >> n;
    vector<vector<int>> a(m, vector<int>(k));
    for(int i = 0; i < m; ++i){
        for(int j = 0; j < k; ++j){
            cin >> a[i][j]; --a[i][j];
        }
    }

    vector<pi> comp;
    vector<vector<int>> gr(1);
    for(int i = 0; i < m; ++i) gr[0].pb(i);
    mt19937 gen(524);
    uniform_int_distribution<int> uid(0, (int)1e18);
    auto rnd = [&](int l, int r){
        assert(l <= r);
        return uid(gen) % (r - l + 1) + l;
    };
    auto addnew = [&](){
        sort(all(comp));

        pi now;
        int rep = 0;
        while(true){
            ++rep;
            if(rep > 100) return 0;
            now = {rnd(0, k - 1), rnd(0, k - 1)};
            if(now[0] > now[1]) swap(now[0], now[1]);
            if(now[0] == now[1]) continue;
            int p = lb(comp, now);
            if(p < sz(comp) && comp[p] == now) continue;
            break;
        }

        comp.pb(now);
        return 1;
    };
    while(sz(comp) < 60){
        int f = 1;
        for(auto&v:gr) if(sz(v) > 1){
            f = 0;
            break;
        }
        if(f) break;

        assert(addnew());
        auto now = comp.back();

        vector<vector<int>> ngr;
        for(auto&v:gr){
            vector<int> x, y;
            for(auto&id:v){
                if(a[id][now[0]] < a[id][now[1]]) x.pb(id);
                else y.pb(id);
            }
            if(sz(x)) ngr.pb(x);
            if(sz(y)) ngr.pb(y);
        }
        swap(gr, ngr);
    }

    int usecomp = sz(comp) < 60;
    unordered_map<int, int> mp;
    vector<int> pid(m);
    vector<vector<int>> plist;
    // usecomp = 0;
    if(usecomp){
        while(sz(comp) + 1 < 60){
            if(!addnew()) break;
        }
        for(int i = 0; i < m; ++i){
            int bt = 0;
            for(int j = 0; j < sz(comp); ++j){
                if(a[i][comp[j][0]] < a[i][comp[j][1]]){
                    bt |= 1ll << j;
                }
            }
            assert(mp.find(bt) == mp.end());
            // cout << bt << endl;
            mp[bt] = i;
        }
    }
    else{
        assert(k <= 10);
        vector<int> perm(k);
        iota(all(perm), 0ll);
        sort(all(a));
        do{
            plist.pb(perm);
        }while(next_permutation(all(perm)));
        for(int i = 0; i < m; ++i){
            pid[i] = lb(plist, a[i]);
        }
    }

    // cout << "USECOMP " << usecomp << endl;
    // for(auto&v:comp){
    //     cout << v[0] << ' ' << v[1] << endl;
    // }
    // for(int i = 0; i < m; ++i){
    //     cout << pid[i] << endl;
    // }

    vector<int> p(n);
    for(int i = 0; i < n; ++i){
        cin >> p[i];
    }

    int ans = -1;
    for(int i = 0; i + k <= n; ++i){
        if(usecomp){
            int bt = 0;
            for(int j = 0; j < sz(comp); ++j){
                if(p[i + comp[j][0]] < p[i + comp[j][1]]){
                    bt |= 1ll << j;
                }
            }
            if(mp.find(bt) != mp.end()){
                ans = mp[bt];
                break;
            }
        }
        else{
            vector<int> srt(k), now(k);
            for(int j = 0; j < k; ++j){
                srt[j] = now[j] = p[i + j];
            }
            sort(all(srt));
            for(int j = 0; j < k; ++j){
                now[j] = lb(srt, now[j]);
            }
            int sid = lb(plist, now);

            int p = lb(pid, sid);
            if(p < m && pid[p] == sid){
                ans = p;
                break;
            }
        }
    }

    if(ans == -1) cout << 0;
    else{
        for(int i = 0; i < k; ++i){
            cout << a[ans][i] + 1 << ' ';
        }
    }

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3596kb

input:

3 2 10
1 2 3
1 3 2
20 35 10 7 99 53 72 33 88 16

output:

1 3 2 

result:

ok single line: '1 3 2 '

Test #2:

score: 0
Accepted
time: 0ms
memory: 3516kb

input:

4 5 10
1 2 3 4
1 2 4 3
3 4 1 2
4 1 2 3
4 2 3 1
19 31 9 1 89 48 63 30 78 12

output:

4 2 3 1 

result:

ok single line: '4 2 3 1 '

Test #3:

score: 0
Accepted
time: 0ms
memory: 3584kb

input:

3 3 7
1 3 2
2 3 1
2 1 3
11 22 33 44 55 66 77

output:

0

result:

ok single line: '0'

Test #4:

score: -100
Runtime Error

input:

10000 10 1000000
1 5001 2 5002 3 5003 4 5004 5 5005 6 5006 7 5007 8 5008 9 5009 10 5010 11 5011 12 5012 13 5013 14 5014 15 5015 16 5016 17 5017 18 5018 19 5019 20 5020 21 5021 22 5022 23 5023 24 5024 25 5025 26 5026 27 5027 28 5028 29 5029 30 5030 31 5031 32 5032 33 5033 34 5034 35 5035 36 5036 37 5...

output:


result: