oj.uz

Submission #648377

# Submission time Handle Problem Language Result Execution time Memory
648377 2022-10-06T09:20:48 Z berr The Collection Game (BOI21_swaps) C++17
35 / 100
 102 ms 4556 KB 
#include <bits/stdc++.h>
#include "swaps.h"
using namespace std;


void solve(int N, int V)
{

    if(V==5000)
    {

        vector<int> vis(N+1);

        vector<int> ans;

        for(int x=0; x<N; x++)
        {
            vector<int> q;
            for(int i=1; i<=N; i++)
            {
                if(!vis[i]) q.push_back(i);
            }

            while(q.size()>1)
            {
                for(int l=0; l<q.size()-1; l+=2)
                {
                    schedule(q[l], q[l+1]);
                }

                auto b=visit();
                vector<int> p;

                for(int l=0; l<b.size(); l++)
                {
                    if(b[l]==1) p.push_back(q[l*2]);
                    else p.push_back(q[l*2+1]);
                }
                if(q.size()%2==1) p.push_back(q[q.size()-1]) ;

                q=p;
            }

            vis[q[0]]=1;
            ans.push_back(q[0]);
        }
        answer(ans);
    }
    else
    {

    vector<array<int, 2>> a[V];
    vector<vector<int>> vis(V, vector<int>(N+1));
 
    vector<vector<int>> c(N+1, vector<int>(N+1));
 
 
 
    for(int i=1; i<=N; i++)
    {
        for(int l=i+1; l<=N; l++)
        {
            int flag=1;
            for(int j=0; j<V&&flag; j++)
            {
                if(vis[j][i]==0&&vis[j][l]==0)
                {
                    a[j].push_back({i, l});
                    vis[j][i]=1;
                    vis[j][l]=1;
                    flag=0;
                }
            }
        }
    }
 
    for(int i=0; i<V&&a[i].size(); i++)
    {
        for(auto l: a[i]) schedule(l[0], l[1]);
        auto b=visit();
 
        for(int l=0; l<a[i].size(); l++)
        {
            if(b[l]==1) c[a[i][l][0]][a[i][l][1]]=1, c[a[i][l][1]][a[i][l][0]]=0;
            else c[a[i][l][0]][a[i][l][1]]=0, c[a[i][l][1]][a[i][l][0]]=1;
        }
    }
 
 
    vector<array<int, 2>> q;
    vector<int> s;
    for(int i=1; i<=N; i++)
    {
        int l=0;
        for(auto j: c[i]) if(j==0) l++;
            q.push_back({l, i});
    }
 
    sort(q.begin(), q.end());
 
    for(auto i: q) s.push_back(i[1]);
 
    answer(s);
    }

}

Compilation message

swaps.cpp: In function 'void solve(int, int)':
swaps.cpp:26:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |                 for(int l=0; l<q.size()-1; l+=2)
      |                              ~^~~~~~~~~~~
swaps.cpp:34:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |                 for(int l=0; l<b.size(); l++)
      |                              ~^~~~~~~~~
swaps.cpp:82:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |         for(int l=0; l<a[i].size(); l++)
      |                      ~^~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Correct
2 Correct 7 ms 208 KB Correct
3 Correct 25 ms 208 KB Correct
4 Correct 76 ms 400 KB Correct
5 Correct 58 ms 312 KB Correct
6 Correct 87 ms 304 KB Correct
7 Correct 71 ms 312 KB Correct
8 Correct 62 ms 312 KB Correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Correct
2 Correct 12 ms 304 KB Correct
3 Correct 20 ms 300 KB Correct
4 Correct 74 ms 300 KB Correct
5 Correct 74 ms 312 KB Correct
6 Correct 87 ms 316 KB Correct
7 Correct 90 ms 304 KB Correct
8 Correct 85 ms 308 KB Correct
9 Correct 91 ms 4556 KB Correct
10 Correct 98 ms 4500 KB Correct
11 Correct 85 ms 4400 KB Correct
12 Correct 84 ms 4396 KB Correct
13 Correct 86 ms 4400 KB Correct

Subtask #3
3.0 / 3.0

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

Subtask #4
2.0 / 2.0

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

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Correct
2 Correct 7 ms 300 KB Correct
3 Correct 33 ms 300 KB Correct
4 Correct 74 ms 424 KB Correct

Subtask #6
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Correct
2 Correct 7 ms 300 KB Correct
3 Correct 33 ms 300 KB Correct
4 Correct 74 ms 424 KB Correct
5 Correct 1 ms 208 KB Correct
6 Correct 9 ms 208 KB Correct
7 Correct 22 ms 304 KB Correct
8 Correct 79 ms 304 KB Correct
9 Correct 77 ms 312 KB Correct
10 Correct 71 ms 316 KB Correct
11 Correct 77 ms 308 KB Correct
12 Correct 66 ms 316 KB Correct
13 Correct 1 ms 208 KB Correct
14 Correct 10 ms 208 KB Correct
15 Correct 21 ms 208 KB Correct
16 Correct 80 ms 456 KB Correct

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Correct
2 Correct 7 ms 208 KB Correct
3 Correct 24 ms 208 KB Correct
4 Correct 53 ms 316 KB Correct
5 Incorrect 94 ms 3376 KB Not correct
6 Halted 0 ms 0 KB -

Subtask #8
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Correct
2 Correct 7 ms 208 KB Correct
3 Correct 24 ms 208 KB Correct
4 Correct 53 ms 316 KB Correct
5 Incorrect 94 ms 3376 KB Not correct
6 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 8 ms 208 KB Correct
3 Correct 27 ms 300 KB Correct
4 Correct 77 ms 424 KB Correct
5 Incorrect 94 ms 3404 KB Not correct
6 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 8 ms 208 KB Correct
3 Correct 27 ms 300 KB Correct
4 Correct 77 ms 424 KB Correct
5 Incorrect 94 ms 3404 KB Not correct
6 Halted 0 ms 0 KB -

Subtask #11
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Correct
2 Correct 7 ms 208 KB Correct
3 Correct 34 ms 208 KB Correct
4 Correct 102 ms 428 KB Correct
5 Incorrect 92 ms 3416 KB Not correct
6 Halted 0 ms 0 KB -

Subtask #12
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Correct
2 Correct 7 ms 208 KB Correct
3 Correct 34 ms 208 KB Correct
4 Correct 102 ms 428 KB Correct
5 Incorrect 92 ms 3416 KB Not correct
6 Halted 0 ms 0 KB -