제출 #833331

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
833331		vjudge1	Exam (eJOI20_exam)	C++14	0 / 100	139 ms	1168 KiB

exam

#include<bits/stdc++.h>
using namespace std;

int main(){
	int n;
	cin>>n;
	
	vector<int> a(n+2),b(n+2),c(n+2);
	map<int,vector<int>> loc;
	map<int,int> mp;
	priority_queue<int> pq;
	
	for(int i=1;i<=n;i++){
		cin>>a[i];
		loc[a[i]].push_back(i);
	}
	
	for(int i=1;i<=n;i++){
		cin>>b[i];
		mp[b[i]]++;
		if(mp[b[i]]==1)pq.push(-b[i]);
	}
	
	while(!pq.empty()){
		int x=-pq.top();
		pq.pop();
		
		if(loc.find(x)==loc.end())continue;
		int first=loc[x][0];
		
		vector<int> tmp_x(n+2),tmp_o(n+2);
		vector<int> prefix_x(n+2),suffix_x(n+2);
		vector<int> prefix_o(n+2),suffix_o(n+2);
		
		for(int i=1;i<=n;i++){
			if(b[i]==x){
				tmp_x[i]=1;
			}
			if(a[i]==b[i]){
				tmp_o[i]=1;
			}
		}
		
		prefix_x[1]=tmp_x[1];
		prefix_o[1]=tmp_o[1];
		for(int i=2;i<=n;i++){
			prefix_x[i]+=prefix_x[i-1]+tmp_x[i];
			prefix_o[i]+=prefix_o[i-1]+tmp_o[i];
		}
		
		suffix_x[n]=tmp_x[n];
		suffix_o[n]=tmp_o[n];
		for(int i=n-1;1<=i;i--){
			suffix_x[i]+=suffix_x[i+1]+tmp_x[i];
			suffix_o[i]+=suffix_o[i+1]+tmp_o[i];
		}
		
		//kiri ke kanan
		for(int k=0;k<loc[x].size();k++){
			/*
				
				1. mentok ke tembok
					perlu biggest (prefix+suffix)  
					
				2. mentok angka lebih besar
					perlu biggest (prefix+suffix) ,dan
					perlu dari i selanjutnya (kalo ada) untuk cek kebelakang
					lalu perlu biggest (prefix+suffix)
					
				3. ketemu angka x di titik selanjutnya
					perlu biggest subarray
					
					
				loop dari loc[x][i] sampai ada salah satu dari tiga
				
			*/
			
			int type=1;
			for(int jj=loc[x][k]+1; jj<=n; jj++){
				if(a[jj]==x){
					type=3;
				}else if(a[jj]>x){
					type=2;
				}
			}
			
			if(type==1){
				/*
					prefix_x[j] - prefix_x[left-1] + suffix[j+1]
				*/
				int left=loc[x][k];
				int ans=0,right;
				for(int j=left; j<=n; j++){
					int tmp=prefix_x[j] - prefix_x[left-1] + suffix_o[j+1];
					if(ans<tmp){
						ans=tmp;
						right=j;
					}
				}
				
				for(int i=left+1;i<=right;i++){
					a[i]=x;
				}
				
			}else if(type==2){
				int left,right;
				left=loc[x][k];
				for(int i=left;i<=n;i++){
					if(a[i]>x){
						right=i;
						break;
					}
				}
				
				//	prefix[i] - prefix[left-1] + suffix[i+1] - suffix[right+1]
				
				
				int tmp_right,ans=0;
				for(int i=left; i<right; i++){
					int tmp=prefix_x[i] - prefix_x[left-1] + suffix_o[i+1] - suffix_o[right+1];
					if(ans<tmp){
						ans=tmp;
						tmp_right=i;
					}	
				}
				for(int i=left; i<=tmp_right; i++){
					a[i]=x;
				}
				
				if(k+1==n)continue;
				
				right=loc[x][k+1];
				
				for(int i=right; 1<=i;i--){
					if(a[i]>x){
						left=i;
						break;
					}
				}
				int tmp_left;
				ans=0;
				for(int i=right; left<i;i--){
					int tmp = prefix_o[i-1] - prefix_o[left-1] + suffix_x[i]-suffix_x[right+1];
					if(ans<tmp){
						ans=tmp;
						tmp_left=i;
					}
				}
				for(int i=right; tmp_left<=i; i--){
					a[i]=x;
				}
			}else if(type==3){
				vector<int> sub(n+2);
				int left=loc[x][k], right= loc[x][k+1];
				int ct=0;
				for(int i=left ; i<=right; i++){
					if(b[i]==x){
						ct++;
						sub[i]=-1;
					}else if(b[i]==a[i]){
						sub[i]=1;
					}
				}
				
				if(ct==0)continue;
				
				int sum=0;
				int tmp_left=left,tmp_right=left;
				int ll,rr;
				int ans=0;
				for(int i=left; i<=right; i++){
					sum+=sub[i];
					
					if(ans<sum){
						ans=sum;
						ll=tmp_left;
						rr=tmp_right;
					}
					
					if(sum<0){
						sum=0;
						tmp_left=tmp_right=i;
					}
				}
				for(int i=left; i<ll ;i++){
					a[i]=x;
				}
				for(int i=right; rr<i ;i--){
					a[i]=x;
				}
			}
		}
		
		//[0] ke kanan
		int right=loc[x][0],left;
		int tmp_ans=0,tmp;
		for(int i=right ; 1<=i; i--){
			if(a[i]>x)break;
			tmp=prefix_o[i-1] + suffix_x[i] - suffix_x[right+1];
			if(tmp_ans<tmp){
				tmp_ans=tmp;
				left=i;
			}
		}
		for(int i=right; left<=i; i--){
			a[i]=x;
		}
		
	}
	
	int ans=0;
	for(int i=1;i<=n;i++){
		if(a[i]==b[i])ans++;
	}
	
//	for(int i=1;i<=n;i++){
//		cout<<a[i]<<" ";
//	}
//	cout<<"\n";
	cout<<ans<<"\n";
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

exam.cpp: In function 'int main()':
exam.cpp:59:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |   for(int k=0;k<loc[x].size();k++){
      |               ~^~~~~~~~~~~~~~
exam.cpp:29:7: warning: unused variable 'first' [-Wunused-variable]
   29 |   int first=loc[x][0];
      |       ^~~~~
exam.cpp:195:23: warning: 'left' may be used uninitialized in this function [-Wmaybe-uninitialized]
  195 |   int right=loc[x][0],left;
      |                       ^~~~
exam.cpp:169:12: warning: 'rr' may be used uninitialized in this function [-Wmaybe-uninitialized]
  169 |     int ll,rr;
      |            ^~
exam.cpp:169:9: warning: 'll' may be used uninitialized in this function [-Wmaybe-uninitialized]
  169 |     int ll,rr;
      |         ^~
exam.cpp:149:30: warning: 'tmp_left' may be used uninitialized in this function [-Wmaybe-uninitialized]
  149 |     for(int i=right; tmp_left<=i; i--){
      |                      ~~~~~~~~^~~
exam.cpp:118:9: warning: 'tmp_right' may be used uninitialized in this function [-Wmaybe-uninitialized]
  118 |     int tmp_right,ans=0;
      |         ^~~~~~~~~
exam.cpp:119:22: warning: 'right' may be used uninitialized in this function [-Wmaybe-uninitialized]
  119 |     for(int i=left; i<right; i++){
      |                     ~^~~~~~
exam.cpp:101:23: warning: 'right' may be used uninitialized in this function [-Wmaybe-uninitialized]
  101 |     for(int i=left+1;i<=right;i++){
      |                      ~^~~~~~~

• Subtask 1: 0 / 14
• Subtask 2: 0 / 12
• Subtask 3: 0 / 13
• Subtask 4: 0 / 23
• Subtask 5: 0 / 16
• Subtask 6: 0 / 22