Submission #706575

#	Time	Username	Problem	Language	Result	Execution time	Memory
706575		asdfasdfasdfasdf	Minerals (JOI19_minerals)	C++14	90 / 100	76 ms	3580 KiB

minerals

#include "minerals.h"
#include <bits/stdc++.h>

using namespace std;

int match[111111];

vector<int> group[2];

void Divide(vector<int> A, vector<int> B, int c)
{
    random_shuffle(A.begin(),A.end());
	random_shuffle(B.begin(),B.end());

	if(A.size()==0)
        return;

	if(A.size()==1)
	{
		match[A[0]]=B[0];
		match[B[0]]=A[0];

		return;
	}

	int pre=0;

	int sz=A.size()/2;

	if(sz==0)
        sz++;

	if(sz==A.size())
        sz--;

	vector<int> A1;
	vector<int> A2;

	vector<int> B1;
	vector<int> B2;

    if(c==1)
    {
        for(int i=0;i<sz;i++)
            pre=Query(A[i]+1);

        for(int i=0;i<A.size();i++)
        {
            if(i<sz)
                A1.push_back(A[i]);
            else
                A2.push_back(A[i]);
        }

        for(int i=0;i<B.size();i++)
        {
            if(A1.size()==B1.size())
                B2.push_back(B[i]);
            else if(A2.size()==B2.size())
                B1.push_back(B[i]);
            else
            {
                int tmp=Query(B[i]+1);

                if(pre!=tmp)
                    B1.push_back(B[i]);
                else
                    B2.push_back(B[i]);

                pre=tmp;
            }
        }
    }
    else
    {
        for(int i=sz;i<A.size();i++)
            pre=Query(A[i]+1);

        for(int i=0;i<A.size();i++)
        {
            if(i<sz)
                A1.push_back(A[i]);
            else
                A2.push_back(A[i]);
        }

        for(int i=0;i<B.size();i++)
        {
            if(A1.size()==B1.size())
                B2.push_back(B[i]);
            else if(A2.size()==B2.size())
                B1.push_back(B[i]);
            else
            {
                int tmp=Query(B[i]+1);

                if(pre!=tmp)
                    B1.push_back(B[i]);
                else
                    B2.push_back(B[i]);

                pre=tmp;
            }
        }
    }

	Divide(A1,B1,0);
	Divide(A2,B2,1);

    return;
}

void Solve(int n)
{
	int pre=0;

	for(int i=0;i<n*2;i++)
    {
		int tmp=Query(i+1);
		if(pre<tmp)
			group[0].push_back(i);
        else
            group[1].push_back(i);

        pre=tmp;
	}

	Divide(group[0],group[1],1);

	for(int i=0;i<n;i++)
		Answer(group[0][i]+1,match[group[0][i]]+1);

	return;
}

Compilation message (stderr)

minerals.cpp: In function 'void Divide(std::vector<int>, std::vector<int>, int)':
minerals.cpp:33:7: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |  if(sz==A.size())
      |     ~~^~~~~~~~~~
minerals.cpp:47:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |         for(int i=0;i<A.size();i++)
      |                     ~^~~~~~~~~
minerals.cpp:55:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |         for(int i=0;i<B.size();i++)
      |                     ~^~~~~~~~~
minerals.cpp:76:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |         for(int i=sz;i<A.size();i++)
      |                      ~^~~~~~~~~
minerals.cpp:79:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |         for(int i=0;i<A.size();i++)
      |                     ~^~~~~~~~~
minerals.cpp:87:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |         for(int i=0;i<B.size();i++)
      |                     ~^~~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 25 / 25
• Subtask 3: 9 / 9
• Subtask 4: 30 / 30
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 5 / 5
• Subtask 8: 5 / 5
• Subtask 9: 0 / 10