oj.uz

Submission #96857

# Submission time Handle Problem Language Result Execution time Memory
96857 2019-02-12T14:03:19 Z Rouge_Hugo Doktor (COCI17_doktor) C++14
90 / 100
 1000 ms 59024 KB 
	#include <bits/stdc++.h>
	using namespace std;
	const int mw=5*100002;
	int pr[mw],a[mw],t[mw];
	map<double,vector<pair<int,int>>>m;
	int main()
	{ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
		int sum=0;
		int n;cin>>n;
		for(int i=1;i<=n;i++)
		{
			cin>>a[i];
			t[a[i]]=i;
			if (a[i]==i)
			{
				sum++;	
			}
			pr[i]=sum;
		}
		for(int i=1;i<=n;i++)
		{
			double u=(a[i]+i)/2.0;
			m[u].push_back({min(a[i],i),max(a[i],i)});
		}
		int mx=0;
		pair<int,int>b;
		for(auto it :m)
		{sum=0;
		sort(m[it.first].begin(),m[it.first].end());
			for(int i=m[it.first].size()-1;i>-1;i--)
			{
				pair<int,int>pp=m[it.first][i];
				if (mx<sum+1+pr[n]-pr[pp.second]+pr[pp.first-1])
				{
				mx=sum+1+pr[n]-pr[pp.second]+pr[pp.first-1];
				b=pp;
				}
			sum++;
			}
		}
		cout<<a[b.first]<<" "<<a[b.second];
			
	 return 0;
	
	}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 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 3 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 896 KB Output is correct
2 Correct 5 ms 640 KB Output is correct

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 1408 KB Output is correct
2 Correct 79 ms 8724 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 8788 KB Output is correct
2 Correct 27 ms 3320 KB Output is correct

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1070 ms 46128 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 597 ms 27128 KB Output is correct
2 Correct 553 ms 59024 KB Output is correct