QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#620564#8527. Power DivisionsbadmintonWA 2384ms101556kbC++143.2kb2024-10-07 19:15:222024-10-07 19:15:23

Judging History

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

  • [2024-10-07 19:15:23]
  • 评测
  • 测评结果:WA
  • 用时:2384ms
  • 内存:101556kb
  • [2024-10-07 19:15:22]
  • 提交

answer

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <ll,ll> pll;
typedef pair <int,int> pii;
typedef pair <int,pii> piii;

#define forr(_a,_b,_c) for(int _a = (_b); _a <= int (_c); ++_a)
#define ford(_a,_b,_c) for(int _a = (_b) + 1; _a --> int (_c);)
#define forf(_a,_b,_c) for(int _a = (_b); _a < int (_c); ++_a)
#define st first
#define nd second
#define pb push_back
#define mp make_pair
#define all(x) begin(x),end(x)
#define mask(i) (1LL << (i))
#define bit(x, i) (((x) >> (i)) & 1)
#define bp __builtin_popcountll
#define file "test"

template<class X, class Y>
    bool minz(X &x, const Y &y) {
        if (x > y) {
            x = y;
            return true;
        } return false;
    }
template<class X, class Y>
    bool maxz(X &x, const Y &y) {
        if (x < y) {
            x = y;
            return true;
        } return false;
    }

const int N = 1e6 + 50;
const ll oo = (ll) 1e16;
const ll mod = 1e9 + 7; // 998244353;

ll rd (ll l, ll r){
    ll res = 0;
    for (int i = 0; i < 4; i++)
        res = (res << 15) ^ rand();
    return res;
}


void add (ll &u, ll v){
    u += v;
    if (u >= mod)
        u -= mod;
}

ll a[N], n, cur, pre[N], pw[N];
ll dp[N], mn, mx;
map <int, int> bit;

void addbit (int x){
    cur ^= pw[x];
    bit[x]++;
    minz(mn, x);

    while (bit[x] > 1){
        bit[x] -= 2;

        if (mn == x)
            mn++;
        bit[++x]++;
        cur ^= pw[x]; 
    }

    maxz(mx, x);
}

void solve (int l, int r){
    if (l == r){
        add(dp[l], dp[l - 1]);
        //cout <<l << " " << r << " " << dp[l] << " zz\n";
        return;
    }

    int mid = (l + r) >> 1;
    solve(l, mid);

    map <ll, ll> g, f;
    cur = 0;
    mn = mx = a[mid];
    bit.clear();
    
    //cout << l << " " << r << ":\n";

    ford (i, mid, l){
        addbit(a[i]);
        add(f[cur], dp[i - 1]);
        ll x = pre[mx] ^ (mn == 0 ? 0 : pre[mn - 1]) ^ pw[mn] ^ cur;
        if (x != cur)
            add(g[x], dp[i - 1]);
        //cout << i << " " << mid << " " << mn << " " << mx << " " << cur << " " << x << " " << dp[i - 1] << "\n"; 
    }

    //cout << "--\n";

    cur = 0;
    mn = mx = a[mid + 1];
    bit.clear();

    forr (i, mid + 1, r){
        addbit(a[i]);
        ll x = pre[mx] ^ (mn == 0 ? 0 : pre[mn - 1]) ^ pw[mn] ^ cur;
        add(dp[i], g[cur]);
        add(dp[i], f[x]);
        //cout << mid + 1 << " " << i << " " << mn << " " << mx << " " << cur << " " << dp[i] << "\n"; 

        //cout << x << " " << pre[mx] << " " << pw[mx] << "\n";
    }

    solve(mid + 1, r);
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    #ifdef hqm
        freopen(file".inp", "r", stdin); freopen(file".out", "w", stdout);
    #endif
    srand(time(NULL));

    cin >> n;

    forr (i, 1, n){
        cin >> a[i];
    }

    pw[0] = pre[0] = rand();

    forr (i, 1, 1000030){
        pw[i] = rand();
        pre[i] = pre[i - 1] ^ pw[i];
    }

    dp[0] = 1;

    solve(1, n);

    forr (i, 0, n){
        //cout << dp[i] << " " << pw[i] << "\n";
    }

    cout << dp[n] << "\n";

    return 0;
}
/*



*/


詳細信息

Test #1:

score: 100
Accepted
time: 6ms
memory: 20028kb

input:

5
2 0 0 1 1

output:

6

result:

ok 1 number(s): "6"

Test #2:

score: 0
Accepted
time: 0ms
memory: 20108kb

input:

1
0

output:

1

result:

ok 1 number(s): "1"

Test #3:

score: 0
Accepted
time: 9ms
memory: 22360kb

input:

2
1 1

output:

2

result:

ok 1 number(s): "2"

Test #4:

score: 0
Accepted
time: 8ms
memory: 20020kb

input:

3
2 1 1

output:

3

result:

ok 1 number(s): "3"

Test #5:

score: 0
Accepted
time: 5ms
memory: 22160kb

input:

4
3 2 2 3

output:

4

result:

ok 1 number(s): "4"

Test #6:

score: 0
Accepted
time: 3ms
memory: 22100kb

input:

5
3 4 4 2 4

output:

2

result:

ok 1 number(s): "2"

Test #7:

score: 0
Accepted
time: 5ms
memory: 22384kb

input:

7
3 4 3 5 6 3 4

output:

6

result:

ok 1 number(s): "6"

Test #8:

score: 0
Accepted
time: 8ms
memory: 22124kb

input:

10
8 6 5 6 7 8 6 8 9 9

output:

4

result:

ok 1 number(s): "4"

Test #9:

score: 0
Accepted
time: 4ms
memory: 22084kb

input:

96
5 1 0 2 5 5 2 4 2 4 4 2 3 4 0 2 1 4 3 1 2 0 2 2 3 2 4 5 3 5 2 0 2 2 5 3 0 4 5 3 5 4 4 3 1 2 0 5 4 5 0 2 3 2 4 0 0 4 2 0 2 5 3 3 1 5 5 1 1 1 0 5 0 3 0 2 1 1 0 5 0 3 3 4 4 5 3 0 2 2 0 5 4 5 0 5

output:

11332014

result:

ok 1 number(s): "11332014"

Test #10:

score: 0
Accepted
time: 10ms
memory: 20188kb

input:

480
2 0 4 4 1 0 0 3 1 1 4 2 5 5 4 2 1 2 4 4 1 3 4 3 0 5 2 0 2 5 1 0 5 0 0 5 5 0 2 5 2 2 3 1 4 3 5 4 5 2 4 4 4 4 1 4 0 3 4 3 4 1 0 4 3 4 5 4 3 5 0 2 2 0 1 5 4 4 2 0 3 3 3 4 3 0 5 5 3 1 5 1 0 1 0 4 3 0 5 1 4 1 4 3 0 1 3 5 0 3 3 1 0 4 1 1 2 0 1 2 0 3 5 2 0 5 5 5 5 3 5 1 0 2 5 2 2 0 2 0 2 3 5 1 2 1 5 4 ...

output:

506782981

result:

ok 1 number(s): "506782981"

Test #11:

score: 0
Accepted
time: 10ms
memory: 22700kb

input:

2400
0 2 2 0 5 4 3 2 3 2 5 4 5 4 4 5 2 2 4 2 2 0 1 0 5 0 4 4 0 0 5 0 4 0 1 3 4 5 0 3 1 0 4 0 2 5 0 3 3 3 3 1 0 5 5 3 1 3 5 2 4 0 5 0 4 5 4 2 2 1 5 2 2 4 1 0 5 1 5 0 1 2 0 0 3 5 4 0 0 1 1 1 4 2 0 5 1 3 3 5 0 4 4 1 5 5 3 4 4 4 0 2 4 0 5 1 3 1 5 0 5 5 1 3 0 3 1 2 0 1 1 3 5 2 3 4 0 3 0 5 4 0 4 3 5 0 5 2...

output:

586570528

result:

ok 1 number(s): "586570528"

Test #12:

score: 0
Accepted
time: 47ms
memory: 22916kb

input:

12000
2 2 1 2 0 2 5 3 2 0 1 3 2 5 4 0 0 5 3 2 0 2 3 4 3 2 1 4 3 0 3 5 4 1 0 2 4 1 3 2 3 5 0 3 0 0 4 0 4 5 1 0 4 1 1 1 5 4 3 0 3 5 4 5 2 5 0 1 2 3 5 5 2 5 4 2 0 4 4 3 0 0 2 5 0 3 4 2 5 4 2 1 4 5 1 1 2 3 0 3 3 3 3 4 0 5 3 4 0 3 0 2 0 0 2 0 3 4 2 2 0 1 0 5 3 0 2 0 2 2 1 0 5 3 5 4 5 5 0 4 0 4 1 4 4 3 2 ...

output:

201653965

result:

ok 1 number(s): "201653965"

Test #13:

score: 0
Accepted
time: 272ms
memory: 36376kb

input:

60000
2 5 0 3 2 3 5 3 5 5 4 1 1 5 3 0 1 1 2 5 5 5 0 3 2 0 3 2 3 3 0 0 1 4 3 1 4 2 3 3 0 5 1 0 1 1 5 5 4 0 5 4 1 3 1 3 5 3 2 4 4 4 5 4 3 2 3 2 4 5 2 0 4 5 1 2 0 4 0 5 1 3 4 1 2 4 1 1 3 3 0 1 1 3 0 0 2 3 3 2 1 4 1 2 4 3 3 5 2 5 3 4 3 0 2 1 1 1 5 1 2 4 2 3 1 2 1 0 2 0 1 1 5 5 3 4 2 5 2 4 5 3 0 5 1 4 2 ...

output:

592751350

result:

ok 1 number(s): "592751350"

Test #14:

score: 0
Accepted
time: 1915ms
memory: 95848kb

input:

300000
0 5 1 5 5 4 5 3 0 5 0 5 1 4 1 2 2 2 3 0 1 5 4 0 3 1 4 5 2 1 0 3 2 1 2 5 0 2 4 5 0 1 2 1 1 0 0 5 3 0 0 3 4 5 0 2 1 1 1 2 5 1 4 3 1 0 2 0 0 4 3 3 2 5 3 3 1 5 2 0 2 4 3 1 0 3 4 1 3 3 1 0 0 1 1 1 3 1 2 3 5 3 3 2 0 3 0 0 5 5 0 0 0 0 1 4 3 3 4 3 4 5 3 3 5 1 1 4 2 2 1 3 2 1 1 0 0 5 5 0 0 3 2 4 5 5 2...

output:

842503795

result:

ok 1 number(s): "842503795"

Test #15:

score: 0
Accepted
time: 1158ms
memory: 64256kb

input:

300000
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...

output:

432100269

result:

ok 1 number(s): "432100269"

Test #16:

score: 0
Accepted
time: 1134ms
memory: 61960kb

input:

300000
1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 10000...

output:

432100269

result:

ok 1 number(s): "432100269"

Test #17:

score: 0
Accepted
time: 1407ms
memory: 72492kb

input:

299995
1 1 0 0 0 1 0 0 1 1 0 1 0 1 0 0 1 1 0 0 1 1 1 0 1 1 0 0 1 0 0 1 1 0 1 0 1 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 0 0 1 0 1 1 1 0 0 1 1 0 1 0 1 1 0 1 0 1 0 1 0 1 1 0 1 0 0 0 0 0 0 1 0 1 1 0 1 1 1 1 0 1 1 1 1 0 0 0 0 0 1 0 1 1 0 0 0 1 0 0 1 1 0 0 1 1 1 1 1 1 0 1 1 0 0 1 0 0 1 0 1 0 1 1 0 0 0...

output:

261818019

result:

ok 1 number(s): "261818019"

Test #18:

score: 0
Accepted
time: 2011ms
memory: 101124kb

input:

299997
2 2 0 9 4 4 2 3 8 9 3 9 1 6 4 0 1 5 1 0 7 9 3 3 8 9 3 8 3 6 9 3 9 5 9 1 4 4 7 5 9 0 7 3 7 2 0 3 3 8 2 1 7 6 8 1 6 1 8 4 7 6 3 6 1 6 8 9 3 8 1 5 0 8 1 10 0 3 4 5 8 5 6 9 2 4 5 0 9 0 9 5 1 0 3 7 5 8 8 10 10 3 3 10 5 8 9 9 7 4 4 1 1 6 5 7 2 5 8 3 3 9 6 4 1 0 2 6 2 8 7 7 10 5 7 8 3 8 5 1 6 6 6 1 ...

output:

999738318

result:

ok 1 number(s): "999738318"

Test #19:

score: -100
Wrong Answer
time: 2384ms
memory: 101556kb

input:

299999
97 34 33 30 15 73 31 69 60 63 79 87 78 13 49 58 23 38 91 28 70 70 14 98 56 59 81 66 29 21 10 51 94 32 41 98 16 48 67 62 55 5 17 81 30 91 39 93 73 74 46 74 41 99 19 10 0 16 72 95 84 40 97 17 76 10 42 50 66 97 4 30 71 74 46 5 75 87 55 82 38 94 14 82 49 10 23 21 19 99 52 100 71 29 64 73 54 88 2 ...

output:

698456106

result:

wrong answer 1st numbers differ - expected: '799664563', found: '698456106'