Submission #238819

#	Time	Username	Problem	Language	Result	Execution time	Memory
238819		kshitij_sodani	Sticks (POI11_pat)	C++17	84 / 100	480 ms	49832 KiB

pat

#include <bits/stdc++.h>
using namespace std;
typedef int64_t llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second


int co[50];
int co2[50];
vector<pair<int,pair<int,int>>> pre;
vector<pair<int,pair<int,int>>> pre2;
int k;
vector<int> bb;
	vector<pair<int,int>> cc;
	//vector<int> indd;
		set<pair<int,int>> cur;
	set<pair<int,int>> cur2;
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>k;
	for(int i=0;i<k;i++){
		co[i]=-1;
		co2[i]=-1;	
	}
	
	for(int i=0;i<k;i++){
		int x;
		cin>>x;
		int aa;
		for(int j=0;j<x;j++){
			cin>>aa;
			cc.pb({aa,i});
			bb.pb(aa);
//			indd.pb(-aa);
		}
		sort(bb.begin(),bb.end());

		for(int j=0;j<x-1;j++){
			if(bb[j]<bb[j+1]){
				pre.pb({bb[j+1]-1,{bb[j],i}});
//				indd.pb(-(bb[j+1]-1));
			}
		}
		pre.pb({1e9,{bb.back(),i}});
//		indd.pb(-1e9);
		pre.pb({bb[0]-1,{-2,i}});
//		indd.pb(-(bb[0]-1));
		for(int j=0;j<x;j++){
//			indd.pb(-bb[j]);
			pre2.pb({bb[j],{bb[j],i}});
		}
		bb.clear();
	}
	sort(cc.begin(),cc.end());
	sort(pre.begin(),pre.end());
	sort(pre2.begin(),pre2.end());

	int ind=(int)(cc.size())-1;
//	sort(indd.begin(),indd.end());
	pair<int,int> j;
	pair<int,int> kk;
	int i;
	while(ind>=0){
		
		i=cc[ind].a;
		if(pre.size()){
			i=max(i,pre.back().a);

		}
		if(pre2.size()){
			i=max(i,pre2.back().a);
		}
		int st=0;
		while(pre2.size()){
			if(pre2.back().a==i){
				j=pre2.back().b;
				if(co2[j.b]>-1){
					cur2.erase({co2[j.b],j.b});
				
				}
				co2[j.b]=j.a;
					cur2.insert({co2[j.b],j.b});
					pre2.pop_back();
				}
			else{
				break;
			}
		}
	/*	for(auto j:pre2[i]){
			
		//		cout<<j.b<<','<<j.a<<endl;
		}*/
		while(pre.size()){
			if(pre.back().a==i){
				j=pre.back().b;
			//	cout<<j.a<<","<<j.b<<endl;
				if(co[j.b]>-1){
					cur.erase({-co[j.b],j.b});
				}
				if(j.a==-2){

					co[j.b]=-1;
					cur.erase({-co[j.b],j.b});
					pre.pop_back();
					continue;
				}
				co[j.b]=j.a;
				cur.insert({-co[j.b],j.b});
					pre.pop_back();
			}
			else{
				break;
			}
		}
		/*for(auto j:pre[i]){
			
	//		cout<<-co[j.b]<<"    "<<j.b<<endl;
			
		}*/
		/*	cout<<i<<endl;
			for(auto j:cur){
				cout<<j.a<<"::"<<j.b<<endl;
			}
			for(auto j:cur2){
				cout<<j.a<<",,"<<j.b<<endl;
			}
			cout<<endl;
*/
		



		while(ind>=0){
			if(cc[ind].a==i){

		//		cout<<ind<<"/"<<endl;
				if(co2[cc[ind].b]>-1){
					cur2.erase({co2[cc[ind].b],cc[ind].b});
				}
				if(co[cc[ind].b]>-1){
					cur.erase({-co[cc[ind].b],cc[ind].b});
				}
				if(cur.size()){
					j=*(cur.begin());
					if(co2[j.b]>-1){
						cur2.erase({co2[j.b],j.b});
					}
					if(cur2.size()>0){
						kk=*(cur2.begin());
						if(kk.a<-j.a+i){
							cout<<j.b+1<<" "<<-j.a<<" "<<kk.b+1<<" "<<kk.a<<" "<<cc[ind].b+1<<" "<<cc[ind].a<<endl;
							return 0;
						}
					}
					if(co2[j.b]>-1){
						cur2.insert({co2[j.b],j.b});
					}
				}
				if(cur2.size()){
					j=*(cur2.begin());
					if(co[j.b]>-1){
						cur.erase({-co[j.b],j.b});
					}
					if(cur.size()>0){
						kk=*(cur.begin());
						if(j.a<-kk.a+i){
							st=1;
							cout<<j.b+1<<" "<<j.a<<" "<<kk.b+1<<" "<<-kk.a<<" "<<cc[ind].b+1<<" "<<cc[ind].a<<endl;
							return 0;
						}
					}
					if(co[j.b]>-1){
						cur.insert({-co[j.b],j.b});
					}
					
				}

				if(co2[cc[ind].b]>-1){
					cur2.insert({co2[cc[ind].b],cc[ind].b});
				}
				if(co[cc[ind].b]>-1){
					cur.insert({-co[cc[ind].b],cc[ind].b});
				}
				ind--;
			}
			else{
				break;
			}
		}

	}

	cout<<"NIE"<<endl;

	return 0;
}

Compilation message (stderr)

pat.cpp: In function 'int main()':
pat.cpp:77:7: warning: variable 'st' set but not used [-Wunused-but-set-variable]
   int st=0;
       ^~

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 7 / 7
• Subtask 4: 7 / 7
• Subtask 5: 8 / 8
• Subtask 6: 8 / 8
• Subtask 7: 8 / 8
• Subtask 8: 8 / 8
• Subtask 9: 8 / 8
• Subtask 10: 8 / 8
• Subtask 11: 8 / 8
• Subtask 12: 0 / 8
• Subtask 13: 0 / 8