QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#711575 | #7949. K-Lottery | kizen# | RE | 0ms | 3596kb | C++20 | 4.2kb | 2024-11-05 12:10:14 | 2024-11-05 12:10:15 |
Judging History
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...