oj.uz

Submission #426295

# Submission time Handle Problem Language Result Execution time Memory
426295 2021-06-13T17:09:46 Z duality The Collection Game (BOI21_swaps) C++14
71 / 100
 614 ms 544 KB 
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
typedef long long int LLI;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pii> vpii;
#include "swaps.h"

int used[500];
void solve(int N,int V) {
    int i,j;
    vi order;
    for (i = 0; i < N; i++) order.pb(i+1);
    random_shuffle(order.begin(),order.end());
    int s = sqrt(N),c = 0;
    for (j = N/4; j > 0; j -= s/2+(rand() & 1)) {
        vi v1,v2;
        for (i = j; i < N; i++) {
            if (!used[i-j]) v1.pb(i),schedule(order[i-j],order[i]),used[i-j] = used[i] = 1;
            else v2.pb(i);
        }
        fill(used,used+N,0);
        vi r = visit();
        for (i = 0; i < r.size(); i++) {
            if (!r[i]) swap(order[v1[i]-j],order[v1[i]]);
        }
        for (i = 0; i < v2.size(); i++) schedule(order[v2[i]-j],order[v2[i]]);
        r = visit();
        for (i = 0; i < r.size(); i++) {
            if (!r[i]) swap(order[v2[i]-j],order[v2[i]]);
        }
        c += 2;
    }
    for (j = 0; j < (V-c)/2; j++) {
        vi v1,v2;
        for (i = 1; i < N; i++) {
            if (i & 1) schedule(order[i-1],order[i]),v1.pb(i);
            else v2.pb(i);
        }
        vi r = visit();
        for (i = 0; i < r.size(); i++) {
            if (!r[i]) swap(order[v1[i]-1],order[v1[i]]);
        }
        for (i = 0; i < v2.size(); i++) schedule(order[v2[i]-1],order[v2[i]]);
        r = visit();
        for (i = 0; i < r.size(); i++) {
            if (!r[i]) swap(order[v2[i]-1],order[v2[i]]);
        }
    }
    answer(order);
}

Compilation message

swaps.cpp: In function 'void solve(int, int)':
swaps.cpp:26:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |         for (i = 0; i < r.size(); i++) {
      |                     ~~^~~~~~~~~~
swaps.cpp:29:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |         for (i = 0; i < v2.size(); i++) schedule(order[v2[i]-j],order[v2[i]]);
      |                     ~~^~~~~~~~~~~
swaps.cpp:31:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |         for (i = 0; i < r.size(); i++) {
      |                     ~~^~~~~~~~~~
swaps.cpp:43:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |         for (i = 0; i < r.size(); i++) {
      |                     ~~^~~~~~~~~~
swaps.cpp:46:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |         for (i = 0; i < v2.size(); i++) schedule(order[v2[i]-1],order[v2[i]]);
      |                     ~~^~~~~~~~~~~
swaps.cpp:48:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |         for (i = 0; i < r.size(); i++) {
      |                     ~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 200 KB Correct
2 Correct 160 ms 292 KB Correct
3 Correct 276 ms 200 KB Correct
4 Correct 594 ms 524 KB Correct
5 Correct 572 ms 500 KB Correct
6 Correct 526 ms 516 KB Correct
7 Correct 566 ms 412 KB Correct
8 Correct 582 ms 500 KB Correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 200 KB Correct
2 Correct 146 ms 316 KB Correct
3 Correct 315 ms 200 KB Correct
4 Correct 563 ms 428 KB Correct
5 Correct 560 ms 396 KB Correct
6 Correct 544 ms 540 KB Correct
7 Correct 594 ms 496 KB Correct
8 Correct 548 ms 500 KB Correct
9 Correct 118 ms 388 KB Correct
10 Correct 111 ms 320 KB Correct
11 Correct 120 ms 424 KB Correct
12 Correct 114 ms 316 KB Correct
13 Correct 126 ms 332 KB Correct

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 200 KB Correct
2 Correct 157 ms 200 KB Correct

Subtask #4
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 200 KB Correct
2 Correct 157 ms 200 KB Correct
3 Correct 71 ms 200 KB Correct
4 Correct 152 ms 200 KB Correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 200 KB Correct
2 Correct 183 ms 200 KB Correct
3 Correct 323 ms 200 KB Correct
4 Correct 540 ms 456 KB Correct

Subtask #6
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 200 KB Correct
2 Correct 183 ms 200 KB Correct
3 Correct 323 ms 200 KB Correct
4 Correct 540 ms 456 KB Correct
5 Correct 51 ms 200 KB Correct
6 Correct 160 ms 200 KB Correct
7 Correct 320 ms 200 KB Correct
8 Correct 614 ms 516 KB Correct
9 Correct 565 ms 520 KB Correct
10 Correct 580 ms 344 KB Correct
11 Correct 544 ms 472 KB Correct
12 Correct 543 ms 452 KB Correct
13 Correct 96 ms 200 KB Correct
14 Correct 149 ms 200 KB Correct
15 Correct 321 ms 256 KB Correct
16 Correct 585 ms 412 KB Correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 200 KB Correct
2 Correct 149 ms 200 KB Correct
3 Correct 309 ms 200 KB Correct
4 Correct 574 ms 468 KB Correct
5 Correct 52 ms 316 KB Correct

Subtask #8
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 200 KB Correct
2 Correct 149 ms 200 KB Correct
3 Correct 309 ms 200 KB Correct
4 Correct 574 ms 468 KB Correct
5 Correct 52 ms 316 KB Correct
6 Correct 73 ms 200 KB Correct
7 Correct 162 ms 200 KB Correct
8 Correct 297 ms 200 KB Correct
9 Correct 549 ms 412 KB Correct
10 Correct 583 ms 456 KB Correct
11 Correct 543 ms 412 KB Correct
12 Correct 560 ms 520 KB Correct
13 Correct 551 ms 468 KB Correct
14 Correct 124 ms 384 KB Correct
15 Correct 103 ms 384 KB Correct
16 Correct 113 ms 412 KB Correct
17 Correct 116 ms 420 KB Correct
18 Correct 107 ms 348 KB Correct
19 Correct 82 ms 200 KB Correct
20 Correct 153 ms 200 KB Correct
21 Correct 287 ms 200 KB Correct
22 Correct 614 ms 388 KB Correct
23 Correct 68 ms 328 KB Correct

Subtask #9
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 200 KB Correct
2 Correct 147 ms 200 KB Correct
3 Correct 294 ms 300 KB Correct
4 Correct 564 ms 532 KB Correct
5 Correct 56 ms 532 KB Correct
6 Correct 11 ms 292 KB Correct

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 200 KB Correct
2 Correct 147 ms 200 KB Correct
3 Correct 294 ms 300 KB Correct
4 Correct 564 ms 532 KB Correct
5 Correct 56 ms 532 KB Correct
6 Correct 11 ms 292 KB Correct
7 Correct 40 ms 200 KB Correct
8 Correct 164 ms 200 KB Correct
9 Correct 313 ms 200 KB Correct
10 Correct 559 ms 544 KB Correct
11 Correct 566 ms 516 KB Correct
12 Correct 609 ms 412 KB Correct
13 Correct 567 ms 456 KB Correct
14 Correct 557 ms 380 KB Correct
15 Correct 115 ms 308 KB Correct
16 Correct 117 ms 400 KB Correct
17 Correct 95 ms 320 KB Correct
18 Correct 115 ms 316 KB Correct
19 Correct 99 ms 504 KB Correct
20 Correct 49 ms 200 KB Correct
21 Correct 175 ms 200 KB Correct
22 Correct 326 ms 256 KB Correct
23 Correct 564 ms 492 KB Correct
24 Correct 55 ms 304 KB Correct
25 Incorrect 11 ms 296 KB Not correct

Subtask #11
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 200 KB Correct
2 Correct 148 ms 200 KB Correct
3 Correct 323 ms 200 KB Correct
4 Correct 569 ms 444 KB Correct
5 Correct 62 ms 396 KB Correct
6 Correct 11 ms 320 KB Correct
7 Incorrect 5 ms 292 KB Not correct

Subtask #12
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 200 KB Correct
2 Correct 148 ms 200 KB Correct
3 Correct 323 ms 200 KB Correct
4 Correct 569 ms 444 KB Correct
5 Correct 62 ms 396 KB Correct
6 Correct 11 ms 320 KB Correct
7 Incorrect 5 ms 292 KB Not correct