QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#817736#2595. Interesting Subsegments通顶雪道 (Qiuyang Mang, Youran Sun, Qingshuo Guo)#AC ✓44ms8988kbC++231.6kb2024-12-17 11:15:282024-12-17 11:15:28

Judging History

This is the latest submission verdict.

  • [2024-12-17 11:15:28]
  • Judged
  • Verdict: AC
  • Time: 44ms
  • Memory: 8988kb
  • [2024-12-17 11:15:28]
  • Submitted

answer

#include <bits/stdc++.h>

using namespace std;

int n;
long long x = -1, y = -1, z = -1;
long long k;

inline long long mySqrt(long long res) {
    long long ret = floor(sqrtl(res));
    for (long long i = ret - 3; i <= ret + 3; ++i)
        if (i >= 0 && i * i == res) return i;
    return -1;
}

inline bool check(long long nx) {
    long long c = n + 1 - nx;
    long long res = 4ll * c * c - 8ll * (c * (c - 1) + nx * (nx - 1) - k * 2);
    if (res < 0) return false;
    res = mySqrt(res);
    if (res < 0) return false;
    if ((c * 2 + res) % 4 != 0) return false;
    long long ny1 = (c * 2 + res) / 4, ny2 = (c * 2 - res) / 4;
    if (ny1 >= 0 && nx + ny1 <= n + 1) {
        x = nx, y = ny1, z = n + 1 - x - y;
        return true;
    }
    if (ny2 >= 0 && nx + ny2 <= n + 1) {
        x = nx, y = ny2, z = n + 1 - x - y;
        return true;
    }
    return false;
}

int main(){
    scanf("%d%lld", &n, &k);
    for (int i = n + 1; i >= 1; --i) {
        if (check(i)) {
            break;
        }
    }

    if (x == -1) {
        puts("-1");
        return 0;
    }

    vector<int> ans;
    for (int i = 0; i < x - 1; ++i) ans.push_back(0);
    if (y) {
        ans.push_back(1);
        for (int i = 0; i < y - 1; ++i) ans.push_back(0);
        if (z) {
            ans.push_back(1);
            for (int i = 0; i < z - 1; ++i) ans.push_back(0);
        }
    }
    else {
        if (z) {
            ans.push_back(2);
            for (int i = 0; i < z - 1; ++i) ans.push_back(0);
        }
    }

    for (auto a: ans) printf("%d ", a); puts("");
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3756kb

input:

5 3

output:

0 1 0 1 0 

result:

ok 5 number(s): "0 1 0 1 0"

Test #2:

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

input:

5 5

output:

-1

result:

ok 1 number(s): "-1"

Test #3:

score: 0
Accepted
time: 39ms
memory: 8988kb

input:

1000000 499999500000

output:

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 0 0 0 ...

result:

ok 1000000 numbers

Test #4:

score: 0
Accepted
time: 2ms
memory: 3636kb

input:

1000000 1000000000

output:

-1

result:

ok 1 number(s): "-1"

Test #5:

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

input:

1 1

output:

0 

result:

ok 1 number(s): "0"

Test #6:

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

input:

1 2

output:

-1

result:

ok 1 number(s): "-1"

Test #7:

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

input:

1 1000000000000000000

output:

-1

result:

ok 1 number(s): "-1"

Test #8:

score: 0
Accepted
time: 2ms
memory: 3656kb

input:

1000000 1000000000000000000

output:

-1

result:

ok 1 number(s): "-1"

Test #9:

score: 0
Accepted
time: 2ms
memory: 3652kb

input:

1000000 1

output:

-1

result:

ok 1 number(s): "-1"

Test #10:

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

input:

5 7

output:

0 0 0 1 0 

result:

ok 5 number(s): "0 0 0 1 0"

Test #11:

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

input:

5 4

output:

0 0 1 0 1 

result:

ok 5 number(s): "0 0 1 0 1"

Test #12:

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

input:

10 24

output:

0 0 0 0 0 0 1 0 0 1 

result:

ok 10 numbers

Test #13:

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

input:

10 27

output:

0 0 0 0 0 0 1 0 0 0 

result:

ok 10 numbers

Test #14:

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

input:

100 1732

output:

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 1 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 1 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 

result:

ok 100 numbers

Test #15:

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

input:

100 1975

output:

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 1 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 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 

result:

ok 100 numbers

Test #16:

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

input:

1000 204910

output:

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 0 0 0 ...

result:

ok 1000 numbers

Test #17:

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

input:

1000 265236

output:

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 0 0 0 ...

result:

ok 1000 numbers

Test #18:

score: 0
Accepted
time: 1ms
memory: 4056kb

input:

10000 25560422

output:

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 0 0 0 ...

result:

ok 10000 numbers

Test #19:

score: 0
Accepted
time: 1ms
memory: 4124kb

input:

10000 26154570

output:

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 0 0 0 ...

result:

ok 10000 numbers

Test #20:

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

input:

100000 3239110096

output:

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 0 0 0 ...

result:

ok 100000 numbers

Test #21:

score: 0
Accepted
time: 2ms
memory: 4084kb

input:

100000 2424821020

output:

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 0 0 0 ...

result:

ok 100000 numbers

Test #22:

score: 0
Accepted
time: 44ms
memory: 8852kb

input:

1000000 209744030050

output:

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 0 0 0 ...

result:

ok 1000000 numbers

Test #23:

score: 0
Accepted
time: 44ms
memory: 8524kb

input:

1000000 215238432908

output:

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 0 0 0 ...

result:

ok 1000000 numbers

Test #24:

score: 0
Accepted
time: 16ms
memory: 5268kb

input:

454641 45004685864

output:

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 0 0 0 ...

result:

ok 454641 numbers

Test #25:

score: 0
Accepted
time: 32ms
memory: 8988kb

input:

879445 136324541542

output:

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 0 0 0 ...

result:

ok 879445 numbers

Test #26:

score: 0
Accepted
time: 40ms
memory: 7640kb

input:

999998 166665833334

output:

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 0 0 0 ...

result:

ok 999998 numbers

Test #27:

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

input:

1 0

output:

1 

result:

ok 1 number(s): "1"

Test #28:

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

input:

2 0

output:

1 1 

result:

ok 2 number(s): "1 1"

Test #29:

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

input:

3 0

output:

-1

result:

ok 1 number(s): "-1"