QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#346039 | #7949. K-Lottery | tuanlinh123 | WA | 926ms | 141824kb | C++20 | 2.4kb | 2024-03-07 19:57:06 | 2024-03-07 19:57:06 |
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=1e9+7;
ll po[1000005], a[1000005];
map <ll, ll> trace;
vector <ll> tick[1005];
namespace SegTree
{
struct Node
{
ll cnt=0, val=0;
Node(){}
Node(ll x): cnt(!!x), val(x){}
Node operator + (const Node &a) const
{
Node ans;
ans.cnt=cnt+a.cnt;
ans.val=(val+a.val*po[cnt])%Mod;
return ans;
}
};
ll n;
vector <Node> St;
void init(ll sz) {n=sz, St.resize(n*4+1);}
void update(ll i, ll Start, ll End, ll idx, ll val)
{
if (Start>idx || End<idx) return;
if (Start==End) {St[i]=Node(val); return;}
ll mid=(Start+End)/2;
if (idx<=mid) update(i*2, Start, mid, idx, val);
if (mid+1<=idx) update(i*2+1, mid+1, End, idx, val);
St[i]=St[i*2]+St[i*2+1];
}
void update(ll idx, ll val) {update(1, 1, n, idx, val);}
ll query() {return St[1].val;}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
ll k, m, n, sum=0; cin >> k >> m >> n;
for (ll i=0; i<=n; i++)
{
po[i]=i?po[i-1]*base%Mod:1;
if (i<k) sum=(sum+po[i])%Mod;
}
for (ll i=1; i<=m; i++)
{
tick[i].resize(k);
ll val=0;
vector <pll> num;
for (ll j=0; j<k; j++)
{
cin >> tick[i][j];
val=(val+tick[i][j]*po[j])%Mod;
}
trace[val]=i;
}
vector <ll> num;
for (ll 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());
SegTree::init(n);
for (ll i=1; i<=n; i++)
{
a[i]=lower_bound(num.begin(), num.end(), a[i])-num.begin()+1;
SegTree::update(a[i], i);
if (i>=k)
{
ll val=(SegTree::query()-(i-k)*sum%Mod+Mod)%Mod;
if (trace[val])
{
ll id=trace[val];
for (ll j:tick[id]) cout << j << " ";
exit(0);
}
SegTree::update(a[i-k+1], 0);
}
}
cout << 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5884kb
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: 1ms
memory: 5672kb
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: 1ms
memory: 5676kb
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
Wrong Answer
time: 926ms
memory: 141824kb
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:
0
result:
wrong answer 1st lines differ - expected: '1 5001 2 5002 3 5003 4 5004 5 ... 4998 9998 4999 9999 5000 10000', found: '0'