oj.uz

Submission #976132

# Submission time Handle Problem Language Result Execution time Memory
976132 2024-05-06T08:11:14 Z happy_node Event Hopping 2 (JOI21_event2) C++17
0 / 100
 3 ms 11612 KB 
#include <bits/stdc++.h>
using namespace std; 

const int MX=4e5+5, inf=1e9;

int N,K;

vector<pair<int,int>> v;
map<int,int> id;
vector<pair<int,int>> cl[MX];

int dp[MX];
bool used[MX];

vector<int> ans;

int M;

bool ok(int l, int r) {
	for(int k=l;k<=r;k++) if(used[k]) return false;
	return true;
}

int f(int x) {
	vector<pair<int,int>> cur;

	if(x!=-1) {
		auto [l,r]=v[x];
		if(!ok(l,r)) return -1e9;

		for(int k=l;k<=r;k++) used[k]=true;
		cur.push_back({l,r});
	}

	for(int k=1;k<=2*N;k++) {
		for(auto [j,id]:cl[k]) {
			if(ok(j,k)) {
				cur.push_back({j,k});
				for(int z=j;z<=k;z++) used[z]=true;
			}
		}
	}

	for(auto [l,r]:cur) {
		for(int k=l;k<=r;k++) used[k]=false;
	}

	return cur.size();
}

int main() {
	cin.tie(0); ios_base::sync_with_stdio(0);

	cin>>N;

	for(int i=0;i<N;i++) {
		int l,r;
		cin>>l>>r;
		v.push_back({l,r});
		id[l]=0;
		id[r]=0;
	}

	int z=1;
	for(auto &[x,y]:id) y=z++;

	for(auto &[l,r]:v) {
		l=id[l];
		r=id[r];
	}
	for(int i=0;i<N;i++) {
		auto [l,r]=v[i];
		cl[r].push_back({l,i});
	}

	M=f(-1);

	for(int i=0;i<N;i++) {
		if(f(i)+ans.size()==M) {
			auto [l,r]=v[i];
			for(int k=l;k<=r;k++) used[k]=true;
			ans.push_back(i);
		}
	}

	cout<<ans.size()<<'\n';
	sort(ans.begin(),ans.end());
	for(auto x:ans) {
		cout<<x+1<<" ";
	}
	cout<<'\n';
}

Compilation message

event2.cpp: In function 'int main()':
event2.cpp:79:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   79 |   if(f(i)+ans.size()==M) {
      |      ~~~~~~~~~~~~~~~^~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 11608 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 1.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 11612 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 11612 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 11608 KB Output isn't correct
2 Halted 0 ms 0 KB -