oj.uz

Submission #579483

# Submission time Handle Problem Language Result Execution time Memory
579483 2022-06-19T08:42:18 Z web Carnival (CEOI14_carnival) C++17
100 / 100
 19 ms 336 KB 
#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <math.h>
using namespace std;

vector<vector<int>> merge(vector<vector<int>> v1, vector<vector<int>> v2)
{
    if(v1.size() == 0)
        return v2;
    if(v2.size() == 0)
        return v1;
    if(v1.size() < v2.size())
        swap(v1,v2);

    for(int j = 0; j<v2.size(); ++j)
    {

        set<int> representativesV1;
        for(int i = 0; i<v1.size(); ++i)
            representativesV1.insert(v1[i][0]);
        
        int result;
        if(representativesV1.size() !=0)
        {
            string output = to_string(representativesV1.size() +1) +" ";
            for(auto el : representativesV1)
                output += to_string(el+1) + " ";
            output += to_string(v2[j][0]+1);
            cout<<output<<endl;
            cin>>result;
        }
        else
        {
            result =0;
        }
        if(result == representativesV1.size())
        {    
            for(int i = 0; i<v1.size(); ++i)
            {
                cout<<2<<" "<<v1[i][0]+1<<" "<<v2[j][0]+1<<endl;
                int res; cin>>res;
                if(res == 1)
                {
                    
                    for(int k = 0; k<v2[j].size(); ++k)
                    {
                        v1[i].push_back(v2[j][k]);

                    }
                    break;
                }
            }
        }   
        else
        {
            v1.push_back(v2[j]);
        }
        
    }
  
    
    return v1;
}

vector<vector<int>> mergeSort(vector<vector<int>> friends)
{
    if(friends.size() == 1)
        return friends;
    if(friends.size() == 0)
        return vector<vector<int>>(0);
    int mid = friends.size()/2;
    vector<vector<int>> sort1 = mergeSort(vector<vector<int>>(friends.begin(), friends.begin() + mid));
    vector<vector<int>> sort2 = mergeSort(vector<vector<int>>(friends.begin() + mid, friends.end()));
    return merge(sort1, sort2);
}



int main()
{
    int numFriendsKnown = 0;
    int numFriendsTotal; cin>>numFriendsTotal;
    vector<vector<int>> fr(numFriendsTotal);
    for(int i = 0; i<numFriendsTotal; ++i)
    {
        fr[i] = {i};
    }
    vector<vector<int>> groups = mergeSort(fr);
    
    for(int i = 0; i<groups.size(); ++i)
    {
        for(int j =0; j<groups[i].size(); ++j)
        {
            fr[groups[i][j]] = {i+1};
        }
    }
    cout<<0<<" ";
    for(int i = 0; i<fr.size(); ++i)
    {
        cout<<fr[i][0]<<" ";
    }
    cout<<endl;

    return 0;
}

Compilation message

carnival.cpp: In function 'std::vector<std::vector<int> > merge(std::vector<std::vector<int> >, std::vector<std::vector<int> >)':
carnival.cpp:17:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     for(int j = 0; j<v2.size(); ++j)
      |                    ~^~~~~~~~~~
carnival.cpp:21:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |         for(int i = 0; i<v1.size(); ++i)
      |                        ~^~~~~~~~~~
carnival.cpp:38:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::set<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |         if(result == representativesV1.size())
      |            ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
carnival.cpp:40:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |             for(int i = 0; i<v1.size(); ++i)
      |                            ~^~~~~~~~~~
carnival.cpp:47:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |                     for(int k = 0; k<v2[j].size(); ++k)
      |                                    ~^~~~~~~~~~~~~
carnival.cpp: In function 'int main()':
carnival.cpp:92:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |     for(int i = 0; i<groups.size(); ++i)
      |                    ~^~~~~~~~~~~~~~
carnival.cpp:94:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |         for(int j =0; j<groups[i].size(); ++j)
      |                       ~^~~~~~~~~~~~~~~~~
carnival.cpp:100:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |     for(int i = 0; i<fr.size(); ++i)
      |                    ~^~~~~~~~~~
carnival.cpp:83:9: warning: unused variable 'numFriendsKnown' [-Wunused-variable]
   83 |     int numFriendsKnown = 0;
      |         ^~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 208 KB Output is correct
2 Correct 19 ms 336 KB Output is correct
3 Correct 12 ms 336 KB Output is correct
4 Correct 8 ms 336 KB Output is correct
5 Correct 4 ms 208 KB Output is correct
6 Correct 3 ms 208 KB Output is correct
7 Correct 12 ms 336 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 208 KB Output is correct
2 Correct 12 ms 336 KB Output is correct
3 Correct 12 ms 208 KB Output is correct
4 Correct 10 ms 336 KB Output is correct
5 Correct 4 ms 208 KB Output is correct
6 Correct 5 ms 328 KB Output is correct
7 Correct 10 ms 328 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 208 KB Output is correct
2 Correct 6 ms 328 KB Output is correct
3 Correct 8 ms 328 KB Output is correct
4 Correct 9 ms 336 KB Output is correct
5 Correct 4 ms 336 KB Output is correct
6 Correct 4 ms 208 KB Output is correct
7 Correct 13 ms 336 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 208 KB Output is correct
2 Correct 4 ms 320 KB Output is correct
3 Correct 14 ms 336 KB Output is correct
4 Correct 9 ms 336 KB Output is correct
5 Correct 6 ms 208 KB Output is correct
6 Correct 7 ms 336 KB Output is correct
7 Correct 16 ms 336 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 208 KB Output is correct
2 Correct 12 ms 328 KB Output is correct
3 Correct 15 ms 336 KB Output is correct
4 Correct 7 ms 332 KB Output is correct
5 Correct 7 ms 336 KB Output is correct
6 Correct 7 ms 336 KB Output is correct
7 Correct 9 ms 324 KB Output is correct