oj.uz

Submission #444425

# Submission time Handle Problem Language Result Execution time Memory
444425 2021-07-14T04:48:06 Z blue The Collection Game (BOI21_swaps) C++17
50 / 100
 72 ms 480 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)
{
    vector<int> a, b;

    for(int i = 0; i < A.size(); i++)
    {
        if(0 <= A[i] && A[i] < N && 0 <= B[i] && B[i] < N)
        {
            a.push_back(A[i]);
            b.push_back(B[i]);
        }
    }

    if(a.size() == 0) return;
    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:15:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |     for(int i = 0; i < A.size(); i++)
      |                    ~~^~~~~~~~~~
swaps.cpp:25:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     for(int i = 0; i < A.size(); i++)
      |                    ~~^~~~~~~~~~
swaps.cpp:32:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     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 15 ms 200 KB Correct
4 Correct 54 ms 304 KB Correct
5 Correct 55 ms 300 KB Correct
6 Correct 54 ms 440 KB Correct
7 Correct 72 ms 304 KB Correct
8 Correct 55 ms 300 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 16 ms 200 KB Correct
4 Correct 57 ms 340 KB Correct
5 Correct 57 ms 300 KB Correct
6 Correct 55 ms 304 KB Correct
7 Correct 56 ms 300 KB Correct
8 Correct 55 ms 300 KB Correct
9 Correct 54 ms 304 KB Correct
10 Correct 54 ms 308 KB Correct
11 Correct 56 ms 316 KB Correct
12 Correct 56 ms 308 KB Correct
13 Correct 56 ms 320 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 4 ms 200 KB Correct
3 Correct 16 ms 276 KB Correct
4 Correct 65 ms 300 KB Correct

Subtask #6
6.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 16 ms 276 KB Correct
4 Correct 65 ms 300 KB Correct
5 Correct 1 ms 200 KB Correct
6 Correct 4 ms 200 KB Correct
7 Correct 15 ms 200 KB Correct
8 Correct 56 ms 308 KB Correct
9 Correct 57 ms 376 KB Correct
10 Correct 57 ms 304 KB Correct
11 Correct 56 ms 300 KB Correct
12 Correct 58 ms 300 KB Correct
13 Correct 1 ms 200 KB Correct
14 Correct 4 ms 200 KB Correct
15 Correct 17 ms 280 KB Correct
16 Correct 56 ms 308 KB Correct

Subtask #7
9.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 16 ms 280 KB Correct
4 Correct 55 ms 304 KB Correct
5 Correct 72 ms 396 KB Correct

Subtask #8
6.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 16 ms 280 KB Correct
4 Correct 55 ms 304 KB Correct
5 Correct 72 ms 396 KB Correct
6 Correct 1 ms 200 KB Correct
7 Correct 5 ms 200 KB Correct
8 Correct 16 ms 276 KB Correct
9 Correct 57 ms 332 KB Correct
10 Correct 60 ms 308 KB Correct
11 Correct 54 ms 480 KB Correct
12 Correct 56 ms 304 KB Correct
13 Correct 58 ms 396 KB Correct
14 Correct 71 ms 368 KB Correct
15 Correct 56 ms 424 KB Correct
16 Correct 69 ms 380 KB Correct
17 Correct 58 ms 304 KB Correct
18 Correct 58 ms 304 KB Correct
19 Correct 1 ms 200 KB Correct
20 Correct 4 ms 200 KB Correct
21 Correct 16 ms 200 KB Correct
22 Correct 57 ms 300 KB Correct
23 Correct 59 ms 368 KB Correct

Subtask #9
0 / 21.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 62 ms 344 KB Correct
5 Correct 54 ms 304 KB Correct
6 Incorrect 12 ms 284 KB Not correct

Subtask #10
0 / 14.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 62 ms 344 KB Correct
5 Correct 54 ms 304 KB Correct
6 Incorrect 12 ms 284 KB Not correct

Subtask #11
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 15 ms 276 KB Correct
4 Correct 54 ms 304 KB Correct
5 Correct 66 ms 376 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 1 ms 200 KB Correct
2 Correct 3 ms 200 KB Correct
3 Correct 15 ms 276 KB Correct
4 Correct 54 ms 304 KB Correct
5 Correct 66 ms 376 KB Correct
6 Incorrect 12 ms 284 KB Not correct
7 Halted 0 ms 0 KB -