Submission #116901

#	Time	Username	Problem	Language	Result	Execution time	Memory
116901		manh9203	Doktor (COCI17_doktor)	C++17	100 / 100	767 ms	63844 KiB

doktor

#include<bits/stdc++.h>
using namespace std;
struct change{
	long l,r,mid,val;
};
bool cmp(change a,change b){
	return a.r-a.l < b.r-b.l;
}
int n,a[500005],ansL,ansR,mx=-1;
long dem[500005][3],cnt[500005];
vector<change> pos;
map<pair<long,long>,bool> check;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		if(a[i]==i){
			cnt[i]=cnt[i-1]+1;
		}else{
			cnt[i]=cnt[i-1];
		}
	}
	for(int i=1;i<=n;i++){
		if(a[i]!=i){
			long l=min(a[i],i);
			long r=max(a[i],i);
			if(check[make_pair(l,r)]==0){
				if(a[l]==r&&a[r]==l){
					pos.push_back({l,r,(l+r)/2,2});
				}else{
					pos.push_back({l,r,(l+r)/2,1});
				}
				check[make_pair(l,r)]=1;
			}
		}
	}
	sort(pos.begin(),pos.end(),cmp);
	ansL=ansR=1;
	for(int i=0;i<pos.size();i++){
		//cout<<pos[i].l<<" "<<pos[i].r<<" "<<pos[i].mid<<" "<<pos[i].val<<endl;
		if((pos[i].r-pos[i].l)%2==1){
			dem[pos[i].mid][0]+=pos[i].val;
			if(cnt[n]+dem[pos[i].mid][0]-(cnt[pos[i].r]-cnt[pos[i].l-1])>mx){
				mx=cnt[n]+dem[pos[i].mid][0]-(cnt[pos[i].r]-cnt[pos[i].l-1]);
				ansL=a[pos[i].l];
				ansR=a[pos[i].r];
			}
		}else{
			dem[pos[i].mid][1]+=pos[i].val;
			if(cnt[n]+dem[pos[i].mid][1]-(cnt[pos[i].r]-cnt[pos[i].l-1])+cnt[pos[i].mid]-cnt[pos[i].mid-1]>mx){
				mx=cnt[n]+dem[pos[i].mid][1]-(cnt[pos[i].r]-cnt[pos[i].l-1])+cnt[pos[i].mid]-cnt[pos[i].mid-1];
				ansL=a[pos[i].l];
				ansR=a[pos[i].r];
			}
		}
	}
	cout<<ansL<<" "<<ansR;
}

Compilation message (stderr)

doktor.cpp: In function 'int main()':
doktor.cpp:39:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<pos.size();i++){
              ~^~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10