QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#346151 | #7949. K-Lottery | tuanlinh123 | WA | 0ms | 7732kb | C++20 | 2.2kb | 2024-03-07 21:19:26 | 2024-03-07 21:19:26 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ld long double
#define sz(a) ((ll)(a).size())
using namespace std;
const ll base=41597, Mod=100000004987;
ll po[1000005], a[1000005];
vector <int> tick[1005];
int n, cnt[4000005];
ll v[4000005];
void init(int sz) {n=sz;}
inline void update(int i, int Start, int End, int idx, int val)
{
if (Start==End) {cnt[i]=!!val, v[i]=val; return;}
int mid=(Start+End)/2;
if (idx<=mid) update(i*2, Start, mid, idx, val);
else update(i*2+1, mid+1, End, idx, val);
cnt[i]=cnt[i*2]+cnt[i*2+1];
v[i]=(v[i*2]+(__int128_t)v[i*2+1]*po[cnt[i*2]])%Mod;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int k, m, n; cin >> k >> m >> n;
ll sum=0;
for (int i=0; i<=n; i++)
{
po[i]=i?po[i-1]*base%Mod:1;
if (i<k) sum=(sum+po[i])%Mod;
}
vector <pair<ll, int>> trace;
for (int i=1; i<=m; i++)
{
tick[i].resize(k);
vector <pair<int, int>> num;
for (int j=0; j<k; j++)
cin >> tick[i][j], num.pb({tick[i][j], j+1});
sort(num.begin(), num.end());
ll val=0;
for (int j=0; j<k; j++)
val=(val+(__int128_t)po[j]*num[j].se)%Mod;
trace.pb({val, i});
}
sort(trace.begin(), trace.end());
vector <int> num;
for (int i=1; i<=n; i++) cin >> a[i], num.pb(a[i]);
sort(num.begin(), num.end());
num.resize(unique(num.begin(), num.end())-num.begin());
init(n);
ll ans=0;
for (int i=1; i<=n; i++)
{
a[i]=lower_bound(num.begin(), num.end(), a[i])-num.begin()+1;
update(1, 1, n, a[i], i);
if (i>=k)
{
ll val=(v[1]-sum*(i-k)%Mod+Mod)%Mod;
auto ptr=lower_bound(trace.begin(), trace.end(), mp(val, 0));
if ((*ptr).fi==val)
{
ll id=(*ptr).se;
for (ll j:tick[ans]) cout << j << " ";
return 0;
}
update(1, 1, n, a[i-k+1], 0);
}
}
cout << 0;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 7732kb
input:
3 2 10 1 2 3 1 3 2 20 35 10 7 99 53 72 33 88 16
output:
result:
wrong answer 1st lines differ - expected: '1 3 2', found: ''