QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#346039#7949. K-Lotterytuanlinh123WA 926ms141824kbC++202.4kb2024-03-07 19:57:062024-03-07 19:57:06

Judging History

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

  • [2024-03-07 19:57:06]
  • 评测
  • 测评结果:WA
  • 用时:926ms
  • 内存:141824kb
  • [2024-03-07 19:57:06]
  • 提交

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'