Submission #417045

# Submission time Handle Problem Language Result Execution time Memory
417045 2021-06-03T11:04:01 Z jamezzz Event Hopping 2 (JOI21_event2) C++14
0 / 100
0 ms 204 KB
#include <bits/stdc++.h>
using namespace std;

#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb emplace_back
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
typedef pair<int,int> ii;

int n,k,l,r;
vector<ii> v,t;
multiset<ii> s;

int num(int x){
	pf("num: %d\n",x);
	t.clear();
	for(int i=x;i<n;++i)t.pb(v[i]);
	sort(all(t),[&](ii &a,ii &b){return a.se<b.se;});
	int curr=-1,cnt=0;
	for(int i=0;i<sz(t);++i){
		if(t[i].fi<curr)continue;
		auto it=s.lower_bound(ii(t[i].fi,0));
		if(it!=s.end()&&(*it).fi<t[i].se)continue;
		if(it!=s.begin()&&t[i].fi<(*--it).se)continue;
		pf("%d %d\n",t[i].fi,t[i].se);
		curr=t[i].se;++cnt;
	}
	return cnt;
}

int main(){
	sf("%d%d",&n,&k);
	for(int i=0;i<n;++i){
		sf("%d%d",&l,&r);
		v.pb(l,r);
	}
	int cnt=1;
	bool pos=false;
	for(int i=0;i<n;++i){
		
		auto it=s.lower_bound(ii(v[i].fi,0));
		if(it!=s.end()&&(*it).fi<v[i].se)continue;
		if(it!=s.begin()&&v[i].fi<(*--it).se)continue;
		
		s.insert(ii(v[i].fi,v[i].se));
		
		int tot=num(i+1)+cnt;
		pf("%d: %d\n",i,tot);
		if(tot>=k){
			pos=true;
			if(cnt==k)break;
			++cnt;
			continue;
		}
		else s.erase(s.find(v[i]));
	}
	if(!pos)pf("-1\n"),exit(0);
	for(ii pr:s)pf("%d %d\n",pr.fi,pr.se);
	for(int i=0;i<n;++i){
		if(s.count(v[i])){
			pf("%d\n",i+1);
			s.erase(s.find(v[i]));
		}
	}
}

/*
5 4
1 3
2 5
8 9
6 8
10 15

4 3
1 4
3 5
4 9
7 10

10 6
77412002 93858605
244306432 318243514
280338037 358494212
439397354 492065507
485779890 529132783
571714810 632053254
659767854 709114867
718405631 733610573
786950301 815106357
878719468 899999649
*/

Compilation message

event2.cpp: In function 'int main()':
event2.cpp:35:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |  sf("%d%d",&n,&k);
      |    ^
event2.cpp:37:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |   sf("%d%d",&l,&r);
      |     ^
# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -