Submission #747758

#	Time	Username	Problem	Language	Result	Execution time	Memory
747758		LIF	Handcrafted Gift (IOI20_gift)	C++14	100 / 100	190 ms	24976 KiB

gift

#include "gift.h"
#include<bits/stdc++.h>
#include<string>
#include<vector>
using namespace std;
int ass[500005];
vector<pair<int,int> > one;

//first step : assort it , such that 1111 , 2222;
int construct(int n, int r, vector<int> a, vector<int> b, std::vector<int> x) {
	int pos = 1;
	for(int i=0;i<r;i++)
    {
    	if(x[i] == 1)one.push_back(make_pair(a[i],b[i]));
    	if(x[i] == 2 && b[i] == a[i])return 0;
	}
	sort(one.begin(),one.end());
	int poss = 1;
	if(one.size()!=0)
	{
		for(int i=0;i<one.size();i++)
		{
			int last = one[i].first;
			int mxr = one[i].second;
			while(one[i].first <= mxr && i<= one.size()-1)
			{
				mxr = max(mxr,one[i].second);
				i++;
			}
			i--;
			for(int j=last;j<=mxr;j++)ass[j] = poss;
			poss++;
		}
	}
	for(int i=0;i<r;i++)
	{
		if(x[i] == 1)continue;
		if(ass[b[i]] == ass[a[i]] && ass[b[i]] != 0)return 0;
	}
	
	
	string s;
	s += "R";
	int lastmax = -1;
	if(ass[0] == 1) lastmax = 1;
	for(int i=1;i<n;i++)
	{
		if(ass[i] == 0)
		{
			if(s[i-1] == 'R')s += "B";
			else s += "R";
			continue;
		}
		if(ass[i] == lastmax)
		{
			s += s[i-1];
			continue;
		}
		if(ass[i] > lastmax)
		{
			lastmax = ass[i];
			if(s[i-1] == 'R')s += "B";
			else s += "R";
			continue;
		}
		
	}
	craft(s);
	
    return 1;
}

Compilation message (stderr)

gift.cpp: In function 'int construct(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
gift.cpp:21:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |   for(int i=0;i<one.size();i++)
      |               ~^~~~~~~~~~~
gift.cpp:25:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |    while(one[i].first <= mxr && i<= one.size()-1)
      |                                 ~^~~~~~~~~~~~~~~
gift.cpp:11:6: warning: unused variable 'pos' [-Wunused-variable]
   11 |  int pos = 1;
      |      ^~~

• Subtask 1: 10 / 10
• Subtask 2: 15 / 15
• Subtask 3: 20 / 20
• Subtask 4: 25 / 25
• Subtask 5: 30 / 30