oj.uz

Submission #426303

# Submission time Handle Problem Language Result Execution time Memory
426303 2021-06-13T17:14:30 Z duality The Collection Game (BOI21_swaps) C++14
85 / 100
 16 ms 420 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);
    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/3+(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:27:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |         for (i = 0; i < r.size(); i++) {
      |                     ~~^~~~~~~~~~
swaps.cpp:30:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |         for (i = 0; i < v2.size(); i++) schedule(order[v2[i]-j],order[v2[i]]);
      |                     ~~^~~~~~~~~~~
swaps.cpp:32:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |         for (i = 0; i < r.size(); i++) {
      |                     ~~^~~~~~~~~~
swaps.cpp:44:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |         for (i = 0; i < r.size(); i++) {
      |                     ~~^~~~~~~~~~
swaps.cpp:47:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |         for (i = 0; i < v2.size(); i++) schedule(order[v2[i]-1],order[v2[i]]);
      |                     ~~^~~~~~~~~~~
swaps.cpp:49:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |         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 5 ms 200 KB Correct
3 Correct 8 ms 300 KB Correct
4 Correct 14 ms 320 KB Correct
5 Correct 14 ms 312 KB Correct
6 Correct 12 ms 316 KB Correct
7 Correct 13 ms 376 KB Correct
8 Correct 12 ms 312 KB Correct

Subtask #2
10.0 / 10.0

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

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 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 2 ms 200 KB Correct
2 Correct 4 ms 200 KB Correct
3 Correct 6 ms 200 KB Correct
4 Correct 14 ms 316 KB Correct

Subtask #6
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 200 KB Correct
4 Correct 14 ms 316 KB Correct
5 Correct 3 ms 200 KB Correct
6 Correct 4 ms 200 KB Correct
7 Correct 7 ms 296 KB Correct
8 Correct 10 ms 300 KB Correct
9 Correct 10 ms 316 KB Correct
10 Correct 13 ms 316 KB Correct
11 Correct 14 ms 312 KB Correct
12 Correct 11 ms 316 KB Correct
13 Correct 1 ms 200 KB Correct
14 Correct 4 ms 200 KB Correct
15 Correct 7 ms 200 KB Correct
16 Correct 16 ms 416 KB Correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 200 KB Correct
2 Correct 3 ms 200 KB Correct
3 Correct 9 ms 200 KB Correct
4 Correct 12 ms 320 KB Correct
5 Correct 11 ms 296 KB Correct

Subtask #8
6.0 / 6.0

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

Subtask #9
21.0 / 21.0

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

Subtask #10
14.0 / 14.0

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

Subtask #11
0 / 9.0

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

Subtask #12
0 / 6.0

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