oj.uz

Submission #426291

# Submission time Handle Problem Language Result Execution time Memory
426291 2021-06-13T17:03:05 Z duality The Collection Game (BOI21_swaps) C++14
50 / 100
 608 ms 640 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) {
        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 36 ms 200 KB Correct
2 Correct 171 ms 200 KB Correct
3 Correct 289 ms 200 KB Correct
4 Correct 528 ms 420 KB Correct
5 Correct 572 ms 368 KB Correct
6 Correct 593 ms 332 KB Correct
7 Correct 589 ms 448 KB Correct
8 Correct 556 ms 420 KB Correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 200 KB Correct
2 Correct 126 ms 292 KB Correct
3 Correct 339 ms 296 KB Correct
4 Correct 595 ms 508 KB Correct
5 Correct 549 ms 376 KB Correct
6 Correct 578 ms 388 KB Correct
7 Correct 533 ms 356 KB Correct
8 Correct 557 ms 540 KB Correct
9 Correct 126 ms 508 KB Correct
10 Correct 107 ms 316 KB Correct
11 Correct 114 ms 444 KB Correct
12 Correct 120 ms 440 KB Correct
13 Correct 114 ms 408 KB Correct

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 200 KB Correct
2 Correct 173 ms 200 KB Correct

Subtask #4
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 200 KB Correct
2 Correct 173 ms 200 KB Correct
3 Correct 56 ms 200 KB Correct
4 Correct 181 ms 300 KB Correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 200 KB Correct
2 Correct 116 ms 200 KB Correct
3 Correct 315 ms 200 KB Correct
4 Correct 600 ms 416 KB Correct

Subtask #6
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 200 KB Correct
2 Correct 116 ms 200 KB Correct
3 Correct 315 ms 200 KB Correct
4 Correct 600 ms 416 KB Correct
5 Correct 35 ms 200 KB Correct
6 Correct 131 ms 200 KB Correct
7 Correct 346 ms 200 KB Correct
8 Correct 608 ms 612 KB Correct
9 Correct 557 ms 372 KB Correct
10 Correct 597 ms 316 KB Correct
11 Correct 538 ms 348 KB Correct
12 Correct 577 ms 416 KB Correct
13 Correct 45 ms 200 KB Correct
14 Correct 170 ms 200 KB Correct
15 Correct 303 ms 200 KB Correct
16 Correct 574 ms 392 KB Correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 200 KB Correct
2 Correct 176 ms 200 KB Correct
3 Correct 339 ms 200 KB Correct
4 Correct 563 ms 396 KB Correct
5 Correct 56 ms 392 KB Correct

Subtask #8
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 200 KB Correct
2 Correct 176 ms 200 KB Correct
3 Correct 339 ms 200 KB Correct
4 Correct 563 ms 396 KB Correct
5 Correct 56 ms 392 KB Correct
6 Correct 79 ms 200 KB Correct
7 Correct 171 ms 200 KB Correct
8 Correct 330 ms 200 KB Correct
9 Correct 582 ms 452 KB Correct
10 Correct 562 ms 508 KB Correct
11 Correct 558 ms 504 KB Correct
12 Correct 521 ms 420 KB Correct
13 Correct 605 ms 640 KB Correct
14 Correct 102 ms 316 KB Correct
15 Correct 102 ms 376 KB Correct
16 Correct 104 ms 312 KB Correct
17 Correct 111 ms 376 KB Correct
18 Correct 113 ms 312 KB Correct
19 Correct 85 ms 200 KB Correct
20 Correct 161 ms 200 KB Correct
21 Correct 295 ms 200 KB Correct
22 Correct 527 ms 500 KB Correct
23 Correct 53 ms 320 KB Correct

Subtask #9
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 200 KB Correct
2 Correct 146 ms 200 KB Correct
3 Correct 292 ms 200 KB Correct
4 Correct 518 ms 464 KB Correct
5 Correct 51 ms 296 KB Correct
6 Incorrect 11 ms 296 KB Not correct

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 200 KB Correct
2 Correct 146 ms 200 KB Correct
3 Correct 292 ms 200 KB Correct
4 Correct 518 ms 464 KB Correct
5 Correct 51 ms 296 KB Correct
6 Incorrect 11 ms 296 KB Not correct

Subtask #11
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 200 KB Correct
2 Correct 144 ms 200 KB Correct
3 Correct 266 ms 200 KB Correct
4 Correct 532 ms 352 KB Correct
5 Correct 69 ms 296 KB Correct
6 Incorrect 13 ms 296 KB Not correct
7 Halted 0 ms 0 KB -

Subtask #12
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 200 KB Correct
2 Correct 144 ms 200 KB Correct
3 Correct 266 ms 200 KB Correct
4 Correct 532 ms 352 KB Correct
5 Correct 69 ms 296 KB Correct
6 Incorrect 13 ms 296 KB Not correct
7 Halted 0 ms 0 KB -