oj.uz

Submission #668921

# Submission time Handle Problem Language Result Execution time Memory
668921 2022-12-05T07:57:21 Z mychecksedad The Collection Game (BOI21_swaps) C++17
36 / 100
 115 ms 620 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int M = 505;

void schedule(int, int);

vector<int> visit();

void answer(std::vector<int>);

int n;
bitset<M> is[M];
vector<bool> used(n+1);
pair<int, int> c[M];

int find_next(int i){
    for(int j = 1; j <= n; ++j){
        if(i!=j && !is[i][j] && !used[j]){
            is[i][j] = 1;
            is[j][i] = 1;
            return j;
        }
    }
    return -1;
}

void solve(int NN, int V){
    n = NN;
    if(V < 1000){
        for(int j = 0; j < n; ++j){
            int k = 1;
            if(j % 2){
                k = 2;
            }
            for(int i = k; i < n; i += 2){
                schedule(i, i + 1);
            }
            visit();
        }

        vector<int> a;
        for(int i = 1; i <= n; ++i) a.pb(i);
        answer(a);
        return;
    }
    for(int i = 1; i <= n; ++i) c[i] = {0, i};
    bool ok = 1;
    for(; ok; ){
        used.clear();
        used.resize(n+1);
        vector<array<int, 2>> v;
        ok = 0;
        for(int j = 1; j <= n; ++j){
            if(!used[j]){
                int nxt = find_next(j);
                if(nxt==-1){
                    continue;
                }
                ok = 1;
                used[nxt] = used[j] = 1;
                schedule(j, nxt);
                v.pb({j, nxt});
            }
        }
        if(!ok) break;
        vector<int> ans = visit();
        for(int i = 0; i < ans.size(); ++i){
            c[v[i][!ans[i]]].first++;
        }
    }



    sort(c + 1, c + 1 + n);
    vector<int> a;
    for(int i = n; i >= 1; --i) a.pb(c[i].second);
    answer(a);
}

Compilation message

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Correct
2 Correct 4 ms 208 KB Correct
3 Correct 19 ms 208 KB Correct
4 Correct 94 ms 336 KB Correct
5 Correct 91 ms 336 KB Correct
6 Correct 94 ms 620 KB Correct
7 Correct 90 ms 432 KB Correct
8 Correct 104 ms 348 KB Correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Correct
2 Correct 4 ms 208 KB Correct
3 Correct 20 ms 208 KB Correct
4 Correct 98 ms 336 KB Correct
5 Correct 89 ms 336 KB Correct
6 Correct 110 ms 408 KB Correct
7 Correct 91 ms 336 KB Correct
8 Correct 90 ms 336 KB Correct
9 Correct 101 ms 428 KB Correct
10 Correct 100 ms 340 KB Correct
11 Correct 106 ms 336 KB Correct
12 Correct 89 ms 444 KB Correct
13 Correct 115 ms 464 KB Correct

Subtask #3
3.0 / 3.0

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

Subtask #4
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Correct
2 Correct 4 ms 208 KB Correct
3 Incorrect 1 ms 208 KB Not correct
4 Halted 0 ms 0 KB -

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Correct
2 Correct 4 ms 208 KB Correct
3 Correct 21 ms 208 KB Correct
4 Correct 94 ms 444 KB Correct

Subtask #6
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Correct
2 Correct 4 ms 208 KB Correct
3 Correct 21 ms 208 KB Correct
4 Correct 94 ms 444 KB Correct
5 Correct 1 ms 208 KB Correct
6 Correct 4 ms 208 KB Correct
7 Correct 19 ms 208 KB Correct
8 Correct 112 ms 340 KB Correct
9 Correct 95 ms 420 KB Correct
10 Correct 90 ms 336 KB Correct
11 Correct 90 ms 336 KB Correct
12 Correct 95 ms 388 KB Correct
13 Incorrect 1 ms 208 KB Not correct
14 Halted 0 ms 0 KB -

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Correct
2 Correct 5 ms 208 KB Correct
3 Correct 19 ms 208 KB Correct
4 Correct 86 ms 340 KB Correct
5 Correct 42 ms 348 KB Correct

Subtask #8
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Correct
2 Correct 5 ms 208 KB Correct
3 Correct 19 ms 208 KB Correct
4 Correct 86 ms 340 KB Correct
5 Correct 42 ms 348 KB Correct
6 Correct 1 ms 208 KB Correct
7 Correct 5 ms 208 KB Correct
8 Correct 19 ms 208 KB Correct
9 Correct 95 ms 344 KB Correct
10 Correct 91 ms 344 KB Correct
11 Correct 99 ms 544 KB Correct
12 Correct 90 ms 332 KB Correct
13 Correct 105 ms 340 KB Correct
14 Correct 94 ms 340 KB Correct
15 Correct 98 ms 336 KB Correct
16 Correct 101 ms 344 KB Correct
17 Correct 96 ms 444 KB Correct
18 Correct 93 ms 460 KB Correct
19 Incorrect 1 ms 208 KB Not correct
20 Halted 0 ms 0 KB -

Subtask #9
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Correct
2 Correct 3 ms 208 KB Correct
3 Correct 19 ms 208 KB Correct
4 Correct 101 ms 408 KB Correct
5 Correct 42 ms 288 KB Correct
6 Runtime error 9 ms 288 KB Execution killed with signal 13
7 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Correct
2 Correct 3 ms 208 KB Correct
3 Correct 19 ms 208 KB Correct
4 Correct 101 ms 408 KB Correct
5 Correct 42 ms 288 KB Correct
6 Runtime error 9 ms 288 KB Execution killed with signal 13
7 Halted 0 ms 0 KB -

Subtask #11
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Correct
2 Correct 4 ms 208 KB Correct
3 Correct 18 ms 208 KB Correct
4 Correct 98 ms 344 KB Correct
5 Correct 43 ms 384 KB Correct
6 Runtime error 8 ms 292 KB Execution killed with signal 13
7 Halted 0 ms 0 KB -

Subtask #12
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Correct
2 Correct 4 ms 208 KB Correct
3 Correct 18 ms 208 KB Correct
4 Correct 98 ms 344 KB Correct
5 Correct 43 ms 384 KB Correct
6 Runtime error 8 ms 292 KB Execution killed with signal 13
7 Halted 0 ms 0 KB -