oj.uz

Submission #408983

# Submission time Handle Problem Language Result Execution time Memory
408983 2021-05-20T00:47:42 Z ly20 The Collection Game (BOI21_swaps) C++17
50 / 100
 571 ms 616 KB 
//
// --- Sample implementation for the task swaps ---
//
// To compile this program with the sample grader, place:
//     swaps.h swaps_sample.cpp sample_grader.cpp
// in a single folder and run:
//     g++ swaps_sample.cpp sample_grader.cpp
// in this folder.
//
#include "swaps.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 510;
vector <int> rs;
int inv[MAXN];
void solve(int N, int V) {
    // TODO implement this function
    int n = N, v = V;
    for(int i = 1; i <= n; i++) {
        rs.push_back(i);
        inv[i] = i - 1;
    }
    for(int j = 0; j < V / 2; j++) {
        vector <pair <int, int> > vs;
        for(int i = 0; i < n; i += 2) {
            if(i + 1 >= n) continue;
            schedule(rs[i], rs[i + 1]);
            vs.push_back(make_pair(rs[i], rs[i + 1]));
        }
        vector <int> qr = visit();
        for(int i = 0; i < vs.size(); i++) {
            if(qr[i] == 0) {
                swap(rs[inv[vs[i].first]], rs[inv[vs[i].second]]);
                swap(inv[vs[i].first], inv[vs[i].second]);
            }
        }
        vs.clear();
        for(int i = 1; i < n; i += 2) {
            if(i + 1 >= n) continue;
            schedule(rs[i], rs[i + 1]);
            vs.push_back(make_pair(rs[i], rs[i + 1]));
        }
        qr = visit();
        for(int i = 0; i < vs.size(); i++) {
            if(qr[i] == 0) {
                swap(rs[inv[vs[i].first]], rs[inv[vs[i].second]]);
                swap(inv[vs[i].first], inv[vs[i].second]);
            }
        }
    }
    answer(rs);
}

Compilation message

swaps.cpp: In function 'void solve(int, int)':
swaps.cpp:31:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |         for(int i = 0; i < vs.size(); i++) {
      |                        ~~^~~~~~~~~~~
swaps.cpp:44:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |         for(int i = 0; i < vs.size(); i++) {
      |                        ~~^~~~~~~~~~~
swaps.cpp:18:16: warning: unused variable 'v' [-Wunused-variable]
   18 |     int n = N, v = V;
      |                ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 200 KB Correct
2 Correct 154 ms 200 KB Correct
3 Correct 293 ms 200 KB Correct
4 Correct 532 ms 452 KB Correct
5 Correct 530 ms 412 KB Correct
6 Correct 527 ms 372 KB Correct
7 Correct 545 ms 412 KB Correct
8 Correct 571 ms 500 KB Correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 200 KB Correct
2 Correct 147 ms 200 KB Correct
3 Correct 277 ms 200 KB Correct
4 Correct 524 ms 468 KB Correct
5 Correct 552 ms 484 KB Correct
6 Correct 529 ms 580 KB Correct
7 Correct 557 ms 396 KB Correct
8 Correct 543 ms 452 KB Correct
9 Correct 109 ms 332 KB Correct
10 Correct 110 ms 304 KB Correct
11 Correct 107 ms 316 KB Correct
12 Correct 111 ms 396 KB Correct
13 Correct 103 ms 388 KB Correct

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 200 KB Correct
2 Correct 159 ms 200 KB Correct

Subtask #4
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 200 KB Correct
2 Correct 159 ms 200 KB Correct
3 Correct 73 ms 200 KB Correct
4 Correct 148 ms 200 KB Correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 200 KB Correct
2 Correct 156 ms 200 KB Correct
3 Correct 270 ms 200 KB Correct
4 Correct 560 ms 436 KB Correct

Subtask #6
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 200 KB Correct
2 Correct 156 ms 200 KB Correct
3 Correct 270 ms 200 KB Correct
4 Correct 560 ms 436 KB Correct
5 Correct 71 ms 200 KB Correct
6 Correct 133 ms 200 KB Correct
7 Correct 279 ms 200 KB Correct
8 Correct 540 ms 528 KB Correct
9 Correct 516 ms 444 KB Correct
10 Correct 538 ms 412 KB Correct
11 Correct 520 ms 408 KB Correct
12 Correct 558 ms 376 KB Correct
13 Correct 61 ms 200 KB Correct
14 Correct 162 ms 200 KB Correct
15 Correct 286 ms 200 KB Correct
16 Correct 554 ms 412 KB Correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 200 KB Correct
2 Correct 143 ms 200 KB Correct
3 Correct 289 ms 200 KB Correct
4 Correct 544 ms 388 KB Correct
5 Correct 50 ms 296 KB Correct

Subtask #8
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 200 KB Correct
2 Correct 143 ms 200 KB Correct
3 Correct 289 ms 200 KB Correct
4 Correct 544 ms 388 KB Correct
5 Correct 50 ms 296 KB Correct
6 Correct 53 ms 200 KB Correct
7 Correct 136 ms 200 KB Correct
8 Correct 300 ms 200 KB Correct
9 Correct 556 ms 512 KB Correct
10 Correct 544 ms 452 KB Correct
11 Correct 535 ms 376 KB Correct
12 Correct 550 ms 396 KB Correct
13 Correct 554 ms 416 KB Correct
14 Correct 115 ms 408 KB Correct
15 Correct 104 ms 540 KB Correct
16 Correct 109 ms 300 KB Correct
17 Correct 113 ms 384 KB Correct
18 Correct 122 ms 376 KB Correct
19 Correct 72 ms 200 KB Correct
20 Correct 143 ms 200 KB Correct
21 Correct 301 ms 200 KB Correct
22 Correct 556 ms 460 KB Correct
23 Correct 60 ms 368 KB Correct

Subtask #9
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 200 KB Correct
2 Correct 149 ms 200 KB Correct
3 Correct 289 ms 200 KB Correct
4 Correct 535 ms 392 KB Correct
5 Correct 55 ms 308 KB Correct
6 Incorrect 11 ms 328 KB Not correct

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 200 KB Correct
2 Correct 149 ms 200 KB Correct
3 Correct 289 ms 200 KB Correct
4 Correct 535 ms 392 KB Correct
5 Correct 55 ms 308 KB Correct
6 Incorrect 11 ms 328 KB Not correct

Subtask #11
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 200 KB Correct
2 Correct 146 ms 200 KB Correct
3 Correct 293 ms 200 KB Correct
4 Correct 544 ms 616 KB Correct
5 Correct 57 ms 292 KB Correct
6 Incorrect 12 ms 284 KB Not correct
7 Halted 0 ms 0 KB -

Subtask #12
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 200 KB Correct
2 Correct 146 ms 200 KB Correct
3 Correct 293 ms 200 KB Correct
4 Correct 544 ms 616 KB Correct
5 Correct 57 ms 292 KB Correct
6 Incorrect 12 ms 284 KB Not correct
7 Halted 0 ms 0 KB -