Submission #652152

#	Time	Username	Problem	Language	Result	Execution time	Memory
652152		victor_gao	Event Hopping 2 (JOI21_event2)	C++17	32 / 100	2154 ms	524288 KiB

event2

//#pragma GCC optimize("Ofast,unroll-loops,O3")
//#pragma GCC optimize("avx,avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,fma,tune=native")
#include<bits/stdc++.h>
//#include<bits/extc++.h>
//#pragma pack(1)
#define fast ios::sync_with_stdio(0); cin.tie(0);
#define int long long
#define pii pair<int,int>
#define x first
#define y second
#define N 100015
using namespace std;
//using namespace __gnu_pbds;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//typedef tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> order_multiset;
//typedef tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> order_set;
struct lisan{
	vector<int>vt;
	void in(int x){ vt.push_back(x); }
	void build(){
		sort(vt.begin(),vt.end());
		vt.resize(unique(vt.begin(),vt.end())-vt.begin());
	}
	int find(int x){ return upper_bound(vt.begin(),vt.end(),x)-vt.begin(); }
}uni;
int n,k;
pii seg[N];
vector<int>ans;
bool run(vector<int>have,int need){
	vector<int>all[2*n+5];
	vector<int>dp(2*n+5,0LL);
	for (auto i:have){
		all[seg[i].x].push_back(seg[i].y);
	}
	for (int i=2*n+1;i>=0;i--){
		dp[i]=max(dp[i],dp[i+1]);
		for (auto j:all[i])
			dp[i]=max(dp[i],dp[j]+1);
	}
	return dp[0]>=need;
}
bool touch(int a,int b){
	if (seg[a].x>seg[b].x) swap(a,b);
	if (seg[a].y>seg[b].x) return 1;
	return 0;
}
void solve(vector<int>have,int need){
	if (need==0) return;
	if (have.empty()) return;
	vector<int>last;
	for (int i=1;i<have.size();i++){
		if (!touch(have[0],have[i]))
			last.push_back(have[i]);
	}
	bool flag=run(last,need-1);
	if (flag){
		ans.push_back(have[0]);
		solve(last,need-1);
	}
	else {
		last.clear();
		for (int i=1;i<have.size();i++)
			last.push_back(have[i]);
		solve(last,need);
	}
}
signed main(){
    fast
    cin>>n>>k;
    for (int i=1;i<=n;i++){
    	cin>>seg[i].x>>seg[i].y;
    	uni.in(seg[i].x); uni.in(seg[i].y);
    }
    uni.build();
    for (int i=1;i<=n;i++){
    	seg[i].x=uni.find(seg[i].x);
    	seg[i].y=uni.find(seg[i].y);
    }
    vector<int>have;
    for (int i=1;i<=n;i++)
    	have.push_back(i);
    solve(have,k);
    if (ans.size()!=k) cout<<"-1\n";
    else {
    	for (auto i:ans)
    		cout<<i<<'\n';
    }
}

Compilation message (stderr)

event2.cpp: In function 'void solve(std::vector<long long int>, long long int)':
event2.cpp:51:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |  for (int i=1;i<have.size();i++){
      |               ~^~~~~~~~~~~~
event2.cpp:62:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |   for (int i=1;i<have.size();i++)
      |                ~^~~~~~~~~~~~
event2.cpp: In function 'int main()':
event2.cpp:83:19: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   83 |     if (ans.size()!=k) cout<<"-1\n";
      |         ~~~~~~~~~~^~~

• Subtask 1: 0 / 7
• Subtask 2: 1 / 1
• Subtask 3: 31 / 31
• Subtask 4: 0 / 61