oj.uz

Submission #238819

# Submission time Handle Problem Language Result Execution time Memory
238819 2020-06-13T05:28:32 Z kshitij_sodani Sticks (POI11_pat) C++17
84 / 100
 480 ms 49832 KB 
#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

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct

Subtask #4
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Oczekiwano NIE

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Oczekiwano NIE
2 Correct 29 ms 1840 KB Output is correct

Subtask #6
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Oczekiwano NIE
2 Correct 34 ms 2632 KB Output is correct

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 640 KB Oczekiwano NIE
2 Correct 92 ms 4744 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 1712 KB Oczekiwano NIE
2 Correct 132 ms 7980 KB Output is correct
3 Correct 91 ms 5080 KB Oczekiwano NIE

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 4040 KB Oczekiwano NIE
2 Correct 210 ms 14428 KB Output is correct
3 Correct 141 ms 8500 KB Oczekiwano NIE

Subtask #10
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 24856 KB Output is correct
2 Correct 288 ms 16536 KB Output is correct
3 Correct 212 ms 11324 KB Oczekiwano NIE

Subtask #11
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 242 ms 22968 KB Output is correct
2 Correct 272 ms 15840 KB Output is correct
3 Correct 282 ms 16588 KB Oczekiwano NIE

Subtask #12
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 476 ms 49832 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
2 Halted 0 ms 0 KB -

Subtask #13
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 480 ms 49212 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
2 Halted 0 ms 0 KB -