QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#688289	#7949. K-Lottery	tamthegod	Compile Error	/	/	C++20	10.2kb	2024-10-30 02:30:51	2024-10-30 02:30:52

Judging History

This is the latest submission verdict.

[2024-10-30 02:30:52]
Judged

Verdict: Compile Error
Time: 0ms
Memory: 0kb

Show

[2024-10-30 02:30:51]
Submitted

answer

#include<bits/stdc++.h>

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,p#include<bits/stdc++.h>

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#define pb push_back
#define fi first
#define se second
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxN = 1e6 + 5;
const int mod = 1e9 + 7;
const ll oo = 1e18;
int k, m, n;
int a[maxN];
vector<vector<int>> vc;
int id[maxN];
const int base = 23543653;
int pw[maxN];
map<int, int> mp;
int inv[maxN];
int poww(int k, int n)
{
    int res = 1;
    while(n)
    {
        if(n & 1) res = (1ll * res * k) % mod;
        k = (1ll * k * k) % mod;
        n /= 2;
    }
    return res;
}
void ReadInput()
{
    pw[0] = 1;
    for(int i=1; i<maxN; i++)
        pw[i] = (1ll * pw[i - 1] * base) % mod;
    cin >> k >> m >> n;
    vc.resize(m + 5, vector<int> (k + 5));
    for(int i=1; i<=m; i++)
        for(int j=1; j<=k; j++)
            cin >> vc[i][j];
    for(int i=1; i<=m; i++)
    {
        for(int j=1; j<=k; j++)
            id[vc[i][j]] = j;
        int val = 0;
        for(int j=1; j<=k; j++)
            val = (val + 1ll * id[j] * pw[j - 1] % mod) % mod;
        mp[val] = i;
    }
    vector<pair<int, int>> val;
    for(int i=1; i<=n; i++)
    {
        cin >> a[i];
        val.pb({a[i], i});
    }

    sort(val.begin(), val.end());

    for(int i=1; i<=n; i++)
        a[val[i - 1].se] = i;
    for(int i=0; i<=n; i++)
        inv[i] = poww(pw[i], mod - 2);
}
int st[4 * maxN], lazy[4 * maxN];
inline void refind(int id)
{

    st[id] = st[id * 2] + st[id * 2 + 1];
    if(st[id] >= mod) st[id] -= mod;
}
inline void down(int id)
{
    int t = lazy[id];
    if(!t) return;
    if(t > 0)
    {
        st[id * 2] = (1ll * st[id * 2] * pw[t]) % mod;
        st[id * 2 + 1] = (1ll * st[id * 2 + 1] * pw[t]) % mod;
    }
    else if(t < 0)
    {
        st[id * 2] = (1ll * st[id * 2] * inv[-t]) % mod;
        st[id * 2 + 1] = (1ll * st[id * 2 + 1] * inv[-t]) % mod;
    }
    lazy[id * 2] += t;
    lazy[id * 2 + 1] += t;
    lazy[id] = 0;
}
void update(int id, int l, int r, int pos, int val)
{
    if(l == r && l == pos)
    {

        st[id] = val;
        return;
    }
    down(id);
    int mid = (l + r) / 2;
    if(pos <= mid) update(id * 2, l, mid, pos, val);
    else update(id * 2 + 1, mid + 1, r, pos, val);
    refind(id);
}
void range_upd(int id, int l, int r, int u, int v, int val)
{
    if(l > v || r < u || !st[id]) return;
    if(l >= u && r <= v)
    {
        if(val > 0) st[id] = (1ll * st[id] * pw[val]) % mod;
        else st[id] = (1ll * st[id] * inv[-val]) % mod;
        lazy[id] += val;
        return;
    }
    int mid = (l + r) / 2;
    down(id);
    range_upd(id * 2, l, mid, u, v, val);
    range_upd(id * 2 + 1, mid + 1, r, u, v, val);
    refind(id);
}
int get(int id, int l, int r, int u, int v)
{
    if(l > v || r < u || !st[id]) return 0;
    if(l >= u && r <= v) return st[id];
    int mid = (l + r) / 2;
    down(id);
    auto L = get(id * 2, l, mid, u, v), R = get(id * 2 + 1, mid + 1, r, u, v);
    int val = L + R;
    if(val >= mod) val -= mod;
    return val;
}
int bit[maxN];
inline void update(int pos, short val)
{
    for(; pos <= n; pos += (pos & (-pos)))
        bit[pos] += val;
}
inline int get(int pos)
{
    int res = 0;
    for(; pos; pos -= (pos & (-pos)))
        res += bit[pos];
    return res;
}
void Solve()
{
    int cur = 0;
    int tmp = 0;
    for(int i=0; i<k; i++)
    {
        tmp += pw[i];
        if(tmp >= mod) tmp -= mod;
    }
    for(int i=1; i<=n; i++)
    {
        if(i > k)
        {
            update(1, 1, n, a[i - k], 0);
            update(a[i - k], -1);
           // range_upd(1, 1, n, a[i - k] + 1, n, -1);
            if(a[i - k] < a[i]) range_upd(1, 1, n, a[i - k] + 1, a[i], -1);
            else if(a[i] - k > a[i]) range_upd(1, 1, n, a[i] + 1, a[i - k], 1);
           // range_upd(1, 1, n, a[i - k] + 1, n, -1);
        }
        update(a[i], 1);
        int val = get(a[i] - 1);
        if(i <= k)
            range_upd(1, 1, n, a[i] + 1, n, 1);
        update(1, 1, n, a[i], (1ll * i * pw[val]) % mod);
        int res = st[1];
        if(i >= k)
        {
            res -= cur;
            if(res < 0) res += mod;
            if(mp[res])
            {
                int i = mp[res];
                for(int j=1; j<=k; j++)
                    cout << vc[i][j] << " ";
                return;
            }
            cur += tmp;
            if(cur >= mod) cur -= mod;
        }
    }
  //  cout << 1.0 * clock() / CLOCKS_PER_SEC;return;
    cout << 0;
}
#define taskname "sol"
int32_t main()
{
    if (fopen(taskname ".inp", "r"))
    {
        freopen(taskname ".inp", "r", stdin);
        //freopen(taskname ".out", "w", stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    //cin >> T;
    for(int itest=1; itest<=T; itest++)
    {
        ReadInput();
        Solve();
    }
}
opcnt")

#define pb push_back
#define fi first
#define se second
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxN = 1e6 + 5;
const int mod = 1e9 + 7;
const ll oo = 1e18;
int k, m, n;
int a[maxN];
vector<vector<int>> vc;
int id[maxN];
const int base = 23543653;
int pw[maxN];
map<int, int> mp;
int inv[maxN];
int poww(int k, int n)
{
    int res = 1;
    while(n)
    {
        if(n & 1) res = (1ll * res * k) % mod;
        k = (1ll * k * k) % mod;
        n /= 2;
    }
    return res;
}
void ReadInput()
{
    pw[0] = 1;
    for(int i=1; i<maxN; i++)
        pw[i] = (1ll * pw[i - 1] * base) % mod;
    cin >> k >> m >> n;
    vc.resize(m + 5, vector<int> (k + 5));
    for(int i=1; i<=m; i++)
        for(int j=1; j<=k; j++)
            cin >> vc[i][j];
    for(int i=1; i<=m; i++)
    {
        for(int j=1; j<=k; j++)
            id[vc[i][j]] = j;
        int val = 0;
        for(int j=1; j<=k; j++)
            val = (val + 1ll * id[j] * pw[j - 1] % mod) % mod;
        mp[val] = i;
    }
    vector<pair<int, int>> val;
    for(int i=1; i<=n; i++)
    {
        cin >> a[i];
        val.pb({a[i], i});
    }

    sort(val.begin(), val.end());

    for(int i=1; i<=n; i++)
        a[val[i - 1].se] = i;
    int tmp = poww(base, mod - 2);
    inv[0] = 1;
    for(int i=1; i<=n; i++)
        inv[i] = (1ll * inv[i - 1] * tmp) % mod;
}
int st[4 * maxN], lazy[4 * maxN];
inline void refind(int id)
{

    st[id] = st[id * 2] + st[id * 2 + 1];
    if(st[id] >= mod) st[id] -= mod;
}
inline void down(int id)
{
    int t = lazy[id];
    if(!t) return;
    if(t > 0)
    {
        st[id * 2] = (1ll * st[id * 2] * pw[t]) % mod;
        st[id * 2 + 1] = (1ll * st[id * 2 + 1] * pw[t]) % mod;
    }
    else if(t < 0)
    {
        st[id * 2] = (1ll * st[id * 2] * inv[-t]) % mod;
        st[id * 2 + 1] = (1ll * st[id * 2 + 1] * inv[-t]) % mod;
    }
    lazy[id * 2] += t;
    lazy[id * 2 + 1] += t;
    lazy[id] = 0;
}
void update(int id, int l, int r, int pos, int val)
{
    if(l == r && l == pos)
    {
        st[id] = val;
        return;
    }
    down(id);
    int mid = (l + r) / 2;
    if(pos <= mid) update(id * 2, l, mid, pos, val);
    else update(id * 2 + 1, mid + 1, r, pos, val);
    refind(id);
}
void range_upd(int id, int l, int r, int u, int v, int val)
{
    if(l > v || r < u || !st[id]) return;
    if(l >= u && r <= v)
    {
        if(val > 0) st[id] = (1ll * st[id] * pw[val]) % mod;
        else st[id] = (1ll * st[id] * inv[-val]) % mod;
        lazy[id] += val;
        return;
    }
    int mid = (l + r) / 2;
    down(id);
    range_upd(id * 2, l, mid, u, v, val);
    range_upd(id * 2 + 1, mid + 1, r, u, v, val);
    refind(id);
}
int get(int id, int l, int r, int u, int v)
{
    if(l > v || r < u || !st[id]) return 0;
    if(l >= u && r <= v) return st[id];
    int mid = (l + r) / 2;
    down(id);
    auto L = get(id * 2, l, mid, u, v), R = get(id * 2 + 1, mid + 1, r, u, v);
    int val = L + R;
    if(val >= mod) val -= mod;
    return val;
}
int bit[maxN];
inline void update(int pos, int val)
{
    for(; pos <= n; pos += (pos & (-pos)))
        bit[pos] += val;
}
inline int get(int pos)
{
    int res = 0;
    for(; pos; pos -= (pos & (-pos)))
        res += bit[pos];
    return res;
}
void Solve()
{
    int cur = 0;
    int tmp = 0;
    for(int i=0; i<k; i++)
    {
        tmp += pw[i];
        if(tmp >= mod) tmp -= mod;
    }
    for(int i=1; i<=n; i++)
    {
        if(i > k)
        {
            update(1, 1, n, a[i - k], 0);
            update(a[i - k], -1);
           // range_upd(1, 1, n, a[i - k] + 1, n, -1);
            if(a[i - k] < a[i]) range_upd(1, 1, n, a[i - k] + 1, a[i], -1);
            else if(a[i] - k > a[i]) range_upd(1, 1, n, a[i] + 1, a[i - k], 1);
           // range_upd(1, 1, n, a[i - k] + 1, n, -1);
        }
        update(a[i], 1);
        int val = get(a[i] - 1);
        if(i <= k)
            range_upd(1, 1, n, a[i] + 1, n, 1);
        update(1, 1, n, a[i], (1ll * i * pw[val]) % mod);
        int res = st[1];
        if(i >= k)
        {
            res -= cur;
            if(res < 0) res += mod;
            if(mp[res])
            {
                int i = mp[res];
                for(int j=1; j<=k; j++)
                    cout << vc[i][j] << " ";
                return;
            }
            cur += tmp;
            if(cur >= mod) cur -= mod;
        }
    }
  //  cout << 1.0 * clock() / CLOCKS_PER_SEC;return;
    cout << 0;
}
#define taskname "sol"
int32_t main()
{
    if (fopen(taskname ".inp", "r"))
    {
        freopen(taskname ".inp", "r", stdin);
        //freopen(taskname ".out", "w", stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    //cin >> T;
    for(int itest=1; itest<=T; itest++)
    {
        ReadInput();
        Solve();
    }
}

源文件, 语言: C++20

詳細信息

answer.code:4:20: warning: missing terminating " character
    4 | #pragma GCC target("avx2,bmi,bmi2,lzcnt,p#include<bits/stdc++.h>
      |                    ^
answer.code:4:20: error: missing terminating " character
    4 | #pragma GCC target("avx2,bmi,bmi2,lzcnt,p#include<bits/stdc++.h>
      |                    ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
answer.code:213:6: warning: missing terminating " character
  213 | opcnt")
      |      ^
answer.code:213:6: error: missing terminating " character
  213 | opcnt")
      |      ^~
answer.code:4:65: warning: ‘#pragma GCC option’ is not a string [-Wpragmas]
    4 | #pragma GCC target("avx2,bmi,bmi2,lzcnt,p#include<bits/stdc++.h>
      |                                                                 ^
answer.code:213:1: error: ‘opcnt’ does not name a type
  213 | opcnt")
      | ^~~~~
answer.code:222:9: error: redefinition of ‘std::mt19937 rng’
  222 | mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
      |         ^~~
answer.code:16:9: note: ‘std::mt19937 rng’ previously declared here
   16 | mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
      |         ^~~
answer.code:223:11: error: redefinition of ‘const int maxN’
  223 | const int maxN = 1e6 + 5;
      |           ^~~~
answer.code:17:11: note: ‘const int maxN’ previously defined here
   17 | const int maxN = 1e6 + 5;
      |           ^~~~
answer.code:224:11: error: redefinition of ‘const int mod’
  224 | const int mod = 1e9 + 7;
      |           ^~~
answer.code:18:11: note: ‘const int mod’ previously defined here
   18 | const int mod = 1e9 + 7;
      |           ^~~
answer.code:225:10: error: redefinition of ‘const ll oo’
  225 | const ll oo = 1e18;
      |          ^~
answer.code:19:10: note: ‘const ll oo’ previously defined here
   19 | const ll oo = 1e18;
      |          ^~
answer.code:226:5: error: redefinition of ‘int k’
  226 | int k, m, n;
      |     ^
answer.code:20:5: note: ‘int k’ previously declared here
   20 | int k, m, n;
      |     ^
answer.code:226:8: error: redefinition of ‘int m’
  226 | int k, m, n;
      |        ^
answer.code:20:8: note: ‘int m’ previously declared here
   20 | int k, m, n;
      |        ^
answer.code:226:11: error: redefinition of ‘int n’
  226 | int k, m, n;
      |           ^
answer.code:20:11: note: ‘int n’ previously declared here
   20 | int k, m, n;
      |           ^
answer.code:227:5: error: redefinition of ‘int a [1000005]’
  227 | int a[maxN];
      |     ^
answer.code:21:5: note: ‘int a [1000005]’ previously declared here
   21 | int a[maxN];
      |     ^
answer.code:228:21: error: redefinition of ‘std::vector<std::vector<int> > vc’
  228 | vector<vector<int>> vc;
      |                     ^~
answer.code:22:21: note: ‘std::vector<std::vector<int> > vc’ previously defined here
   22 | vector<vector<int>> vc;
      |                     ^~
answer.code:229:5: error: redefinition of ‘int id [1000005]’
  229 | int id[maxN];
      |     ^~
answer.code:23:5: note: ‘int id [1000005]’ previously declared here
   23 | int id[maxN];
      |     ^~
answer.code:230:11: error: redefinition of ‘const int base’
  230 | const int base = 23543653;
      |           ^~~~
answer.code:24:11: note: ‘const int base’ previously defined here
   24 | const int base = 23543653;
      |           ^~~~
answer.code:231:5: error: redefinition of ‘int pw [1000005]’
  231 | int pw[maxN];
      |     ^~
answer.code:25:5: note: ‘int pw [1000005]’ previously declared here
   25 | int pw[maxN];
      |     ^~
answer.code:232:15: error: redefinition of ‘std::map<int, int> mp’
  232 | map<int, int> mp;
      |               ^~
answer.code:26:15: note: ‘std::map<int, int> mp’ previously declared here
   26 | map<int, int> mp;
      |               ^~
answer.code:233:5: error: redefinition of ‘int inv [1000005]’
  233 | int inv[maxN];
      |     ^~~
answer.code:27:5: note: ‘int inv [1000005]’ previously declared here
   27 | int inv[maxN];
      |     ^~~
answer.code:234:5: error: redefinition of ‘int poww(int, int)’
  234 | int poww(int k, int n)
      |     ^~~~
answer.code:28:5: note: ‘int poww(int, int)’ previously defined here
   28 | int poww(int k, int n)
      |     ^~~~
answer.code:245:6: error: redefinition of ‘void ReadInput()’
  245 | void ReadInput()
      |      ^~~~~~~~~
answer.code:39:6: note: ‘void ReadInput()’ previously defined here
   39 | void ReadInput()
      |      ^~~~~~~~~
answer.code:280:5: error: redefinition of ‘int st [4000020]’
  280 | int st[4 * maxN], lazy[4 * maxN];
      |     ^~
answer.code:72:5: note: ‘int st [4000020]’ previously declared here
   72 | int st[4 * maxN], lazy[4 * maxN];
      |     ^~
answer.code:280:19: error: redefinition of ‘int lazy [4000020]’
  280 | int st[4 * maxN], lazy[4 * maxN];
      |                   ^~~~
answer.code:72:19: note: ‘int lazy [4000020]’ previously declared here
   72 | int st[4 * maxN], lazy[4 * maxN];
      |                   ^~~~
answer.code:281:13: ...