oj.uz

Submission #444416

# Submission time Handle Problem Language Result Execution time Memory
444416 2021-07-14T04:37:11 Z blue The Collection Game (BOI21_swaps) C++17
50 / 100
 65 ms 428 KB 
#include "swaps.h"
#include <vector>
#include <iostream>
using namespace std;

int N;
int V;

vector<int> r;

void do_comparisons(vector<int> A, vector<int> B)
{
    for(int i = 0; i < A.size(); i++)
    {
        schedule(r[ A[i] ], r[ B[i] ]);
    }

    vector<int> C = visit();

    for(int i = 0; i < A.size(); i++)
    {
        if(C[i] == 0)
            swap(r[ A[i] ], r[ B[i] ]);
    }
}


void solve(int n, int v)
{
    N = n;
    V = v;
    r = vector<int>(N);
    for(int i = 1; i <= N; i++) r[i - 1] = i;


    for(int v = 1; v <= min(V, N); v++)
    {
        vector<int> A, B;
        if(v % 2 == 0)
        {
            for(int i = 0; i+1 < N; i += 2)
            {
                A.push_back(i);
                B.push_back(i+1);
            }
        }
        else
        {
            for(int i = 1; i+1 < N; i += 2)
            {
                A.push_back(i);
                B.push_back(i+1);
            }
        }

        do_comparisons(A, B);
    }

    // for(int X = 2; X <= N; X *= 2)
    // {
    //     // cerr << "X = " << X << '\n';
    //     int p = 0, q = X-1;
    //     vector<int> A, B;
    //     while(p < N)
    //     {
    //         for(int i = 0; i < X/2; i++)
    //         {
    //             if(p + i < N && 0 <= q - i && q - i < N)
    //             {
    //                 A.push_back(p + i);
    //                 B.push_back(q - i);
    //             }
    //         }
    //
    //         p += X;
    //         q += X;
    //     }
    //
    //     do_comparisons(A, B);
    //     A.clear();
    //     B.clear();
    //
    //
    //
    //
    //     for(int Y = X/2; Y >= 2; Y /= 2)
    //     {
    //         for(int i = 0; i + Y/2 < N; i++)
    //         {
    //             if((i / (Y/2)) % 2 == 0)
    //             {
    //                 A.push_back(i);
    //                 B.push_back(i + Y/2);
    //             }
    //         }
    //         do_comparisons(A, B);
    //         A.clear();
    //         B.clear();
    //     }
    // }

    answer(r);
}

Compilation message

swaps.cpp: In function 'void do_comparisons(std::vector<int>, std::vector<int>)':
swaps.cpp:13:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |     for(int i = 0; i < A.size(); i++)
      |                    ~~^~~~~~~~~~
swaps.cpp:20:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for(int i = 0; i < A.size(); i++)
      |                    ~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Correct 4 ms 200 KB Correct
3 Correct 16 ms 200 KB Correct
4 Correct 57 ms 296 KB Correct
5 Correct 54 ms 300 KB Correct
6 Correct 63 ms 340 KB Correct
7 Correct 57 ms 400 KB Correct
8 Correct 55 ms 296 KB Correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Correct 4 ms 200 KB Correct
3 Correct 15 ms 200 KB Correct
4 Correct 60 ms 300 KB Correct
5 Correct 54 ms 336 KB Correct
6 Correct 54 ms 300 KB Correct
7 Correct 51 ms 364 KB Correct
8 Correct 55 ms 376 KB Correct
9 Correct 56 ms 300 KB Correct
10 Correct 55 ms 392 KB Correct
11 Correct 54 ms 368 KB Correct
12 Correct 56 ms 300 KB Correct
13 Correct 56 ms 292 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 1 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 1 ms 200 KB Correct
2 Correct 3 ms 200 KB Correct
3 Correct 17 ms 200 KB Correct
4 Correct 55 ms 400 KB Correct

Subtask #6
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Correct 3 ms 200 KB Correct
3 Correct 17 ms 200 KB Correct
4 Correct 55 ms 400 KB Correct
5 Correct 1 ms 200 KB Correct
6 Correct 4 ms 200 KB Correct
7 Correct 16 ms 200 KB Correct
8 Correct 55 ms 388 KB Correct
9 Correct 62 ms 300 KB Correct
10 Correct 52 ms 300 KB Correct
11 Correct 54 ms 336 KB Correct
12 Correct 56 ms 300 KB Correct
13 Correct 1 ms 200 KB Correct
14 Correct 4 ms 200 KB Correct
15 Correct 16 ms 200 KB Correct
16 Correct 58 ms 304 KB Correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Correct 3 ms 200 KB Correct
3 Correct 16 ms 200 KB Correct
4 Correct 54 ms 304 KB Correct
5 Correct 51 ms 296 KB Correct

Subtask #8
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Correct 3 ms 200 KB Correct
3 Correct 16 ms 200 KB Correct
4 Correct 54 ms 304 KB Correct
5 Correct 51 ms 296 KB Correct
6 Correct 1 ms 200 KB Correct
7 Correct 3 ms 288 KB Correct
8 Correct 21 ms 200 KB Correct
9 Correct 65 ms 392 KB Correct
10 Correct 65 ms 336 KB Correct
11 Correct 52 ms 296 KB Correct
12 Correct 53 ms 300 KB Correct
13 Correct 61 ms 376 KB Correct
14 Correct 54 ms 300 KB Correct
15 Correct 53 ms 304 KB Correct
16 Correct 58 ms 300 KB Correct
17 Correct 54 ms 368 KB Correct
18 Correct 54 ms 300 KB Correct
19 Correct 1 ms 200 KB Correct
20 Correct 4 ms 200 KB Correct
21 Correct 15 ms 200 KB Correct
22 Correct 55 ms 332 KB Correct
23 Correct 58 ms 292 KB Correct

Subtask #9
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Correct 3 ms 200 KB Correct
3 Correct 19 ms 200 KB Correct
4 Correct 55 ms 384 KB Correct
5 Correct 60 ms 428 KB Correct
6 Incorrect 11 ms 276 KB Not correct

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Correct 3 ms 200 KB Correct
3 Correct 19 ms 200 KB Correct
4 Correct 55 ms 384 KB Correct
5 Correct 60 ms 428 KB Correct
6 Incorrect 11 ms 276 KB Not correct

Subtask #11
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Correct 4 ms 200 KB Correct
3 Correct 15 ms 200 KB Correct
4 Correct 62 ms 404 KB Correct
5 Correct 60 ms 300 KB Correct
6 Incorrect 11 ms 280 KB Not correct
7 Halted 0 ms 0 KB -

Subtask #12
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Correct 4 ms 200 KB Correct
3 Correct 15 ms 200 KB Correct
4 Correct 62 ms 404 KB Correct
5 Correct 60 ms 300 KB Correct
6 Incorrect 11 ms 280 KB Not correct
7 Halted 0 ms 0 KB -