oj.uz

답안 #82237

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
82237 2018-10-29T15:15:16 Z Genezio Doktor (COCI17_doktor) C++14
60 / 100
 268 ms 40684 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

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

 pii ans;
 int m;
 vector<int> e[N];
 vector<int> o[N];
 int v[N];
 int pre[N];
 int pos[N];

int main() {
	ios::sync_with_stdio(false);
 	cin.tie(0);
    int n,t=0;
    int ptfix=-1;
    cin>>n;
    for(int i=1;i<=n;i++) {
        cin>>v[i];
        pre[i]=pre[i-1];
        if(v[i]==i) ptfix=i,pre[i]++;
        if(abs(v[i]-i)%2) {
        	e[(v[i]+i)>>1].push_back(i);
        	//pos[i]=e[(v[i]+i)>>1].size();
        } else {
        	o[(v[i]+i)>>1].push_back(i);
        	//pos[i]=e[(v[i]+i)>>1].size();
        }
    }
    for(int i=1;i<=n;i++) {
  		if(abs(v[i]-i)%2) {
  			vector<int>::iterator it = lower_bound(e[(v[i]+i)>>1].begin(),e[(v[i]+i)>>1].end(),max(v[i],i));
  			vector<int>::iterator hit = lower_bound(e[(v[i]+i)>>1].begin(),e[(v[i]+i)>>1].end(),min(v[i],i)-1);
  			int a=it-hit+1;
  			//cout<<i<<" "<<a<<" ";
  			a-=(pre[max(v[i],i)]-pre[min(v[i],i)-1]);
  			//cout<<a<<"\n";
  			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];
  				}
  			}
 		} else {
 			vector<int>::iterator it = lower_bound(o[(v[i]+i)>>1].begin(),o[(v[i]+i)>>1].end(),max(v[i],i));
 			vector<int>::iterator hit = lower_bound(o[(v[i]+i)>>1].begin(),o[(v[i]+i)>>1].end(),min(v[i],i)-1);
  			int a=it-hit+1;
  			//cout<<i<<" "<<a<<" ";
  			a-=(pre[max(v[i],i)]-pre[min(v[i],i)-1]);
  			//cout<<a<<"\n";
  			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:26:11: warning: unused variable 't' [-Wunused-variable]
     int n,t=0;
           ^

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 23800 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 23932 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 23952 KB Output is correct
2 Correct 23 ms 23996 KB Output is correct

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 24044 KB Output is correct
2 Incorrect 24 ms 24192 KB Output isn't correct

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 25 ms 24192 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 24192 KB Output is correct
2 Incorrect 23 ms 24192 KB Output isn't correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 24392 KB Output is correct
2 Correct 115 ms 28224 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 56 ms 28224 KB Output is correct
2 Correct 52 ms 28224 KB Output is correct

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 268 ms 40684 KB Output is correct
2 Correct 159 ms 40684 KB Output is correct

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 162 ms 40684 KB Output isn't correct
2 Halted 0 ms 0 KB -