oj.uz

Submission #426299

# Submission time Handle Problem Language Result Execution time Memory
426299 2021-06-13T17:12:50 Z duality The Collection Game (BOI21_swaps) C++14
71 / 100
 15 ms 416 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) {
    V = min(V,100);
    srand(1234);
    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:28:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |         for (i = 0; i < r.size(); 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 < v2.size(); i++) schedule(order[v2[i]-j],order[v2[i]]);
      |                     ~~^~~~~~~~~~~
swaps.cpp:33:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |         for (i = 0; i < r.size(); i++) {
      |                     ~~^~~~~~~~~~
swaps.cpp:45:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |         for (i = 0; i < r.size(); 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 < v2.size(); i++) schedule(order[v2[i]-1],order[v2[i]]);
      |                     ~~^~~~~~~~~~~
swaps.cpp:50:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |         for (i = 0; i < r.size(); i++) {
      |                     ~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 200 KB Correct
2 Correct 4 ms 200 KB Correct
3 Correct 7 ms 200 KB Correct
4 Correct 10 ms 316 KB Correct
5 Correct 11 ms 304 KB Correct
6 Correct 11 ms 320 KB Correct
7 Correct 11 ms 312 KB Correct
8 Correct 10 ms 316 KB Correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 200 KB Correct
2 Correct 4 ms 200 KB Correct
3 Correct 7 ms 300 KB Correct
4 Correct 14 ms 316 KB Correct
5 Correct 11 ms 312 KB Correct
6 Correct 12 ms 392 KB Correct
7 Correct 11 ms 316 KB Correct
8 Correct 10 ms 316 KB Correct
9 Correct 11 ms 320 KB Correct
10 Correct 12 ms 312 KB Correct
11 Correct 11 ms 312 KB Correct
12 Correct 11 ms 320 KB Correct
13 Correct 13 ms 308 KB Correct

Subtask #3
3.0 / 3.0

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

Subtask #4
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 200 KB Correct
2 Correct 4 ms 200 KB Correct
3 Correct 2 ms 200 KB Correct
4 Correct 4 ms 200 KB Correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 200 KB Correct
2 Correct 3 ms 292 KB Correct
3 Correct 8 ms 200 KB Correct
4 Correct 12 ms 312 KB Correct

Subtask #6
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 200 KB Correct
2 Correct 3 ms 292 KB Correct
3 Correct 8 ms 200 KB Correct
4 Correct 12 ms 312 KB Correct
5 Correct 2 ms 200 KB Correct
6 Correct 4 ms 200 KB Correct
7 Correct 6 ms 200 KB Correct
8 Correct 12 ms 312 KB Correct
9 Correct 12 ms 312 KB Correct
10 Correct 12 ms 312 KB Correct
11 Correct 12 ms 316 KB Correct
12 Correct 12 ms 320 KB Correct
13 Correct 2 ms 200 KB Correct
14 Correct 3 ms 200 KB Correct
15 Correct 8 ms 200 KB Correct
16 Correct 14 ms 312 KB Correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 200 KB Correct
2 Correct 4 ms 200 KB Correct
3 Correct 6 ms 296 KB Correct
4 Correct 11 ms 316 KB Correct
5 Correct 12 ms 328 KB Correct

Subtask #8
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 200 KB Correct
2 Correct 4 ms 200 KB Correct
3 Correct 6 ms 296 KB Correct
4 Correct 11 ms 316 KB Correct
5 Correct 12 ms 328 KB Correct
6 Correct 3 ms 200 KB Correct
7 Correct 4 ms 200 KB Correct
8 Correct 9 ms 200 KB Correct
9 Correct 11 ms 316 KB Correct
10 Correct 15 ms 312 KB Correct
11 Correct 12 ms 312 KB Correct
12 Correct 13 ms 312 KB Correct
13 Correct 14 ms 312 KB Correct
14 Correct 11 ms 356 KB Correct
15 Correct 11 ms 312 KB Correct
16 Correct 11 ms 312 KB Correct
17 Correct 11 ms 312 KB Correct
18 Correct 15 ms 292 KB Correct
19 Correct 2 ms 200 KB Correct
20 Correct 4 ms 200 KB Correct
21 Correct 6 ms 200 KB Correct
22 Correct 11 ms 316 KB Correct
23 Correct 13 ms 308 KB Correct

Subtask #9
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 200 KB Correct
2 Correct 5 ms 200 KB Correct
3 Correct 7 ms 200 KB Correct
4 Correct 14 ms 312 KB Correct
5 Correct 12 ms 296 KB Correct
6 Correct 13 ms 292 KB Correct

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 200 KB Correct
2 Correct 5 ms 200 KB Correct
3 Correct 7 ms 200 KB Correct
4 Correct 14 ms 312 KB Correct
5 Correct 12 ms 296 KB Correct
6 Correct 13 ms 292 KB Correct
7 Correct 2 ms 200 KB Correct
8 Correct 4 ms 200 KB Correct
9 Correct 6 ms 200 KB Correct
10 Correct 11 ms 312 KB Correct
11 Correct 11 ms 308 KB Correct
12 Correct 12 ms 308 KB Correct
13 Correct 11 ms 312 KB Correct
14 Correct 11 ms 312 KB Correct
15 Correct 11 ms 316 KB Correct
16 Correct 11 ms 316 KB Correct
17 Correct 11 ms 316 KB Correct
18 Correct 13 ms 312 KB Correct
19 Correct 12 ms 316 KB Correct
20 Correct 2 ms 200 KB Correct
21 Correct 4 ms 296 KB Correct
22 Correct 8 ms 200 KB Correct
23 Correct 12 ms 416 KB Correct
24 Correct 12 ms 300 KB Correct
25 Incorrect 13 ms 408 KB Not correct

Subtask #11
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 200 KB Correct
2 Correct 4 ms 200 KB Correct
3 Correct 7 ms 200 KB Correct
4 Correct 10 ms 312 KB Correct
5 Correct 12 ms 304 KB Correct
6 Correct 11 ms 300 KB Correct
7 Incorrect 7 ms 288 KB Not correct

Subtask #12
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 200 KB Correct
2 Correct 4 ms 200 KB Correct
3 Correct 7 ms 200 KB Correct
4 Correct 10 ms 312 KB Correct
5 Correct 12 ms 304 KB Correct
6 Correct 11 ms 300 KB Correct
7 Incorrect 7 ms 288 KB Not correct