oj.uz

Submission #116898

# Submission time Handle Problem Language Result Execution time Memory
116898 2019-06-14T03:58:21 Z manh9203 Doktor (COCI17_doktor) C++17
50 / 100
 725 ms 63664 KB 
#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=0;
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,(r+l)/2,2});
				}else{
					pos.push_back({l,r,(r+l)/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++){
		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

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

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 640 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 896 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
10.0 / 10.0

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

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 1628 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 12124 KB Output is correct
2 Correct 62 ms 6216 KB Output is correct

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 725 ms 63664 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 389 ms 37564 KB Output isn't correct
2 Halted 0 ms 0 KB -