CSES - Datatähti 2025 loppu

Submission details
Task:	Leikkijät
Sender:	vgtcross
Submission time:	2025-01-18 16:36:30 +0200
Language:	C++ (C++20)
Status:	READY
Result:	100

Feedback
group	verdict	score
#1	ACCEPTED	5
#2	ACCEPTED	8
#3	ACCEPTED	10
#4	ACCEPTED	29
#5	ACCEPTED	37
#6	ACCEPTED	11

Test results
test	verdict	time	group
#1	ACCEPTED	0.00 s	1, 2, 5, 6	details
#2	ACCEPTED	0.00 s	1, 2, 3, 5, 6	details
#3	ACCEPTED	0.00 s	1, 2, 5, 6	details
#4	ACCEPTED	0.00 s	1, 2, 4, 5, 6	details
#5	ACCEPTED	0.00 s	2, 5, 6	details
#6	ACCEPTED	0.01 s	2, 3, 5, 6	details
#7	ACCEPTED	0.00 s	2, 5, 6	details
#8	ACCEPTED	0.01 s	2, 4, 5, 6	details
#9	ACCEPTED	0.00 s	5, 6	details
#10	ACCEPTED	0.04 s	6	details
#11	ACCEPTED	0.00 s	1, 2, 5, 6	details
#12	ACCEPTED	0.03 s	6	details
#13	ACCEPTED	0.00 s	3, 5, 6	details
#14	ACCEPTED	0.00 s	3, 5, 6	details
#15	ACCEPTED	0.00 s	4, 5, 6	details
#16	ACCEPTED	0.00 s	5, 6	details
#17	ACCEPTED	0.05 s	6	details
#18	ACCEPTED	0.00 s	4, 5, 6	details
#19	ACCEPTED	0.00 s	5, 6	details
#20	ACCEPTED	0.04 s	6	details
#21	ACCEPTED	0.05 s	6	details
#22	ACCEPTED	0.00 s	5, 6	details

Compiler report

input/code.cpp: In function 'int get_n(int, int)':
input/code.cpp:15:16: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   15 |     x ^= 1 << k-1;
      |               ~^~
input/code.cpp:20:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   20 |         bool b = (x >> i+1 & 1) ^ (x >> i & 1);
      |                        ~^~
input/code.cpp:22:44: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   22 |         if (!(x >> i & 1) && b) m -= 1 << i+1;
      |                                           ~^~
input/code.cpp:25:16: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   25 |     m %= 1 << k-1;
      |               ~^~
input/code.cpp: In function 'void solve()':
input/code.cpp:42:28: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   42 |             if (b < (1 << k+1)) {
      |                           ~^~
input/code.cpp:52:28: warning: suggest parentheses around '-' inside...

Code

#include <bits/stdc++.h>

#define debug(x) cout << #x << ": " << x << endl
#define fi first
#define se second
#define all(x) begin(x),end(x)
#define rall(x) rbegin(x),rend(x)

using namespace std;
using ll = long long;
using pii = pair<int, int>;

int get_n(int x, int k) {
    if (k == 0) return -1;
    x ^= 1 << k-1;
    if (x & 1) return -1;
    
    int m = 0;
    for (int i = k-2; i >= 0; --i) {
        bool b = (x >> i+1 & 1) ^ (x >> i & 1);
        m += b << i;
        if (!(x >> i & 1) && b) m -= 1 << i+1;
    }
    if (m < 0) m += 1 << k;
    m %= 1 << k-1;
    return m;
}

void solve() {
    int a, b;
    cin >> a >> b;
    --a;--b;

    if (a == b) {
        cout << "-1\n";
        return;
    }

    int n = 1e9;
    for (int k = 1;; ++k) {
        if (a % (1 << k) != b % (1 << k)) {
            if (b < (1 << k+1)) {
                int m = get_n(b, k+1);
                if (m == -1) break;
                int p = 0;
                int c = max(a, b);
                if (c - m >= 0) p = ((c - m) >> k) + 1;
                if (m + (p << k) <= a + (1 << k)) {
                    n = min(n, m + (p << k));
                }

                m ^= 1 << k-1;
                p = 0;
                if (c - m >= 0) p = ((c - m) >> k) + 1;
                if (m + (p << k) <= min(a + (1 << k), b ^ 1 << k)) {
                    n = min(n, m + (p << k));
                }
            }
            break;
        }
    }

    if (a < b) {
        int d = b - a;
        if (!(d & d-1)) {
            int k = 0;
            while ((1 << k) < d) ++k;
            int m = get_n(a % d, k);
            if (m != -1) {
                int p = 0;
                if (b - m >= 0) p = ((b - m) >> k-1) + 1;
                n = min(n, m + (p << k-1));
            }
        }
    }

    cout << (n == 1e9 ? -1 : n) << '\n';
}

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    
    int t;
    cin >> t;
    while (t--) solve();
}

Test details

Test 1

Group: 1, 2, 5, 6

Verdict: ACCEPTED

input
`1000 42 100 73 94 1 13 31 100 ...` view save

correct output
`-1 -1 -1 -1 -1 ...` view save

user output
`-1 -1 -1 -1 -1 ...` Truncated

Test 2

Group: 1, 2, 3, 5, 6

Verdict: ACCEPTED

input
`1000 54 3 42 44 30 1 52 3 ...` view save

correct output
`54 44 31 52 15 ...` view save

user output
`54 44 31 52 15 ...` Truncated

Test 3

Group: 1, 2, 5, 6

Verdict: ACCEPTED

input
`1000 27 25 81 65 45 43 87 23 ...` view save

correct output
`-1 -1 -1 139 -1 ...` view save

user output
`-1 -1 -1 139 -1 ...` Truncated

Test 4

Group: 1, 2, 4, 5, 6

Verdict: ACCEPTED

input
`1000 55 63 39 71 95 96 61 69 ...` view save

correct output
`65 75 -1 72 98 ...` view save

user output
`65 75 -1 72 98 ...` Truncated

Test 5

Group: 2, 5, 6

Verdict: ACCEPTED

input
`1000 222 56 871 832 207 364 919 980 ...` view save

correct output
`-1 -1 -1 -1 -1 ...` view save

user output
`-1 -1 -1 -1 -1 ...` Truncated

Test 6

Group: 2, 3, 5, 6

Verdict: ACCEPTED

input
`1000 892 3 332 334 820 822 42 1 ...` view save

correct output
`892 334 822 43 108 ...` view save

user output
`892 334 822 43 108 ...` Truncated

Test 7

Group: 2, 5, 6

Verdict: ACCEPTED

input
`1000 77 93 319 575 509 381 675 707 ...` view save

correct output
`98 607 574 713 919 ...` view save

user output
`98 607 574 713 919 ...` Truncated

Test 8

Group: 2, 4, 5, 6

Verdict: ACCEPTED

input
`1000 969 985 233 489 403 659 427 555 ...` view save

correct output
`992 500 777 565 261 ...` view save

user output
`992 500 777 565 261 ...` Truncated

Test 9

Group: 5, 6

Verdict: ACCEPTED

input
`1000 10375 364462 501875 499131 495774 7544 133830 316225 ...` view save

correct output
`-1 -1 -1 -1 -1 ...` view save

user output
`-1 -1 -1 -1 -1 ...` Truncated

Test 10

Group: 6

Verdict: ACCEPTED

input
`100000 771321 298762 20752 494590 633649 443015 748804 831912 ...` view save

correct output
`-1 -1 -1 -1 -1 ...` view save

user output
`-1 -1 -1 -1 -1 ...` Truncated

Test 11

Group: 1, 2, 5, 6

Verdict: ACCEPTED

input
`900 1 1 1 2 1 3 1 4 ...` view save

correct output
`-1 -1 3 -1 5 ...` view save

user output
`-1 -1 3 -1 5 ...` Truncated

Test 12

Group: 6

Verdict: ACCEPTED

input
`90000 1 1 1 2 1 3 1 4 ...` view save

correct output
`-1 -1 3 -1 5 ...` view save

user output
`-1 -1 3 -1 5 ...` Truncated

Test 13

Group: 3, 5, 6

Verdict: ACCEPTED

input
`1000 237542 859435 965750 179154 972602 758585 453450 751662 ...` view save

correct output
`-1 -1 -1 -1 -1 ...` view save

user output
`-1 -1 -1 -1 -1 ...` Truncated

Test 14

Group: 3, 5, 6

Verdict: ACCEPTED

input
`1000 773164 1 870426 1 309736 309738 957602 957604 ...` view save

correct output
`773165 870427 309738 957604 513118 ...` view save

user output
`773165 870427 309738 957604 513118 ...` Truncated

Test 15

Group: 4, 5, 6

Verdict: ACCEPTED

input
`1000 178896 591355 54364 110987 361539 818612 275401 926643 ...` view save

correct output
`-1 -1 -1 -1 -1 ...` view save

user output
`-1 -1 -1 -1 -1 ...` Truncated

Test 16

Group: 5, 6

Verdict: ACCEPTED

input
`1000 704481 704465 696919 688727 941011 949203 171023 171025 ...` view save

correct output
`-1 -1 951785 -1 -1 ...` view save

user output
`-1 -1 951785 -1 -1 ...` Truncated

Test 17

Group: 6

Verdict: ACCEPTED

input
`100000 67901 133437 637521 637537 742567 742569 864043 864044 ...` view save

correct output
`148638 637540 -1 -1 652457 ...` view save

user output
`148638 637540 -1 -1 652457 ...` Truncated

Test 18

Group: 4, 5, 6

Verdict: ACCEPTED

input
`1000 650375 650377 181841 443985 750137 750138 256969 322505 ...` view save

correct output
`-1 484136 -1 341476 850152 ...` view save

user output
`-1 484136 -1 341476 850152 ...` Truncated

Test 19

Group: 5, 6

Verdict: ACCEPTED

input
`1000 1 3 1 5 1 9 1 17 ...` view save

correct output
`3 5 10 20 40 ...` view save

user output
`3 5 10 20 40 ...` Truncated

Test 20

Group: 6

Verdict: ACCEPTED

input
`100000 1 3 1 5 1 9 1 17 ...` view save

correct output
`3 5 10 20 40 ...` view save

user output
`3 5 10 20 40 ...` Truncated

Test 21

Group: 6

Verdict: ACCEPTED

input
`100000 999999 1 999999 3 999999 5 999999 7 ...` view save

correct output
`1000002 1000005 1000000 1000011 1000001 ...` view save

user output
`1000002 1000005 1000000 1000011 1000001 ...` Truncated

Test 22

Group: 5, 6

Verdict: ACCEPTED

input
`1000 999999 1 999999 3 999999 5 999999 7 ...` view save

correct output
`1000002 1000005 1000000 1000011 1000001 ...` view save

user output
`1000002 1000005 1000000 1000011 1000001 ...` Truncated

Datatähti 2025 loppu

Leikkijät

Compiler report

Code

Test details

Test 1

Test 2

Test 3

Test 4

Test 5

Test 6

Test 7

Test 8

Test 9

Test 10

Test 11

Test 12

Test 13

Test 14

Test 15

Test 16

Test 17

Test 18

Test 19

Test 20

Test 21

Test 22

Tasks

Submissions (vgtcross)