oj.uz

Submission #82289

# Submission time Handle Problem Language Result Execution time Memory
82289 2018-10-29T18:20:01 Z Genezio Doktor (COCI17_doktor) C++14
100 / 100
 399 ms 43048 KB 
#include<bits/stdc++.h>

using namespace std;
#define pii pair<int,int>
#define mp make_pair
#define F first
#define S second
#define pb push_back
#define ll long long
#define mid ((l+r)>>1)

const int N = 500010;
const int INF = 0x3f3f3f3f;
const ll mod = 1e9+7;

 pii ans;
 int m;
 vector<int> e[2*N];
 int v[N];
 int pre[N];
 //int pos[N];

 /*int bs(vector<int> s,int l,int r,int val) {
 	if(l==r) {
 		return l;
 	}
 	if(s[mid]<val) {

 	}
 }*/

int main() {
	//ios::sync_with_stdio(false);
 	//cin.tie(0);
    int n,t=0;
    int ptfix=-1;
    cin>>n;
    if(n==1) {
    	cin>>n;
    	cout<<"1 1\n";
    	return 0;
    }
    for(int i=1;i<=n;i++) {
        cin>>v[i];
        pre[i]=pre[i-1];
        if(v[i]==i) ptfix=i,pre[i]++;
        e[v[i]+i].push_back(i);
    }
    for(int i=1;i<=n;i++) {
  		vector<int>::iterator it = upper_bound(e[v[i]+i].begin(),e[v[i]+i].end(),max(v[i],i));
  		vector<int>::iterator hit = lower_bound(e[v[i]+i].begin(),e[v[i]+i].end(),min(v[i],i)-1);
  		int a=it-hit;
  		a-=(pre[max(v[i],i)]-pre[min(v[i],i)-1]);
  		if(a>m) {
  			m=a;
  			if(v[i]>i) {
  				ans.F=v[i];
  				ans.S=v[v[i]];
  			} else {
  				ans.F=v[v[i]];
  				ans.S=v[i];
  			}
  		}
    }
    if(m) {
    	cout<<ans.F<<" "<<ans.S<<"\n";
    } else {
    	cout<<ptfix<<" "<<ptfix<<"\n";
    }
}

Compilation message

doktor.cpp: In function 'int main()':
doktor.cpp:35:11: warning: unused variable 't' [-Wunused-variable]
     int n,t=0;
           ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23928 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23928 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 24000 KB Output is correct
2 Correct 22 ms 24000 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 24096 KB Output is correct
2 Correct 25 ms 24096 KB Output is correct

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 24188 KB Output is correct
2 Correct 23 ms 24188 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 24300 KB Output is correct
2 Correct 186 ms 28256 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 28256 KB Output is correct
2 Correct 77 ms 28256 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 399 ms 39228 KB Output is correct
2 Correct 300 ms 39228 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 224 ms 39228 KB Output is correct
2 Correct 275 ms 43048 KB Output is correct