QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#346151#7949. K-Lotterytuanlinh123WA 0ms7732kbC++202.2kb2024-03-07 21:19:262024-03-07 21:19:26

Judging History

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

  • [2024-03-07 21:19:26]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:7732kb
  • [2024-03-07 21:19:26]
  • 提交

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: ''