oj.uz

Submission #87687

# Submission time Handle Problem Language Result Execution time Memory
87687 2018-12-01T22:42:08 Z jasony123123 Doktor (COCI17_doktor) C++11
100 / 100
 396 ms 43532 KB 
/*
Mail.Ru Cup 2018 Round 3
https://codeforces.com/contests/1056
*/
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
//using namespace __gnu_pbds;

#define FOR(i,start,end) for(int i=start;i<(int)(end);i++)
#define FORE(i,start,end) for(int i=start;i<=(int)end;i++)
#define RFOR(i,start,end) for(int i = start; i>end; i--)
#define RFORE(i,start,end) for(int i = start; i>=end; i--)
#define vsort(a) sort(a.begin(), a.end());
#define mp make_pair
#define v vector
#define sf scanf
#define pf printf

typedef long long ll;
typedef pair<int, int > pii;
//template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
void io();

const int MAXN = 500010;

int N;
int A[MAXN];
int pref[MAXN];
v<pii> splits[MAXN * 2];

int main() {

	cin >> N;
	FORE(i, 1, N) {
		cin >> A[i];
		pii swit = { i, A[i] };
		if (i > A[i])
			swap(swit.first, swit.second);
		splits[i + A[i]].push_back(swit);
		pref[i] = pref[i - 1] + (i == A[i] ? 1 : 0);
	}

	int ans = pref[N];
	pii best = { 1,1 };

	FORE(s, 2, 2 * N) if (splits[s].size() > 0) {
		sort(splits[s].begin(), splits[s].end(), greater<pii>());
		FOR(i, 0, splits[s].size()) {
			pii intv = splits[s][i];
			int numG = i + 1 + pref[N] - (pref[intv.second] - pref[intv.first - 1]);
			if (numG > ans) {
				ans = numG;
				best = intv;
			}
		}
	}

	cout << A[best.first] << " " << A[best.second] << "\n";
	return 0;
}

void io() {
#ifndef ONLINE_JUDGE
	freopen("input.in", "r", stdin);
	freopen("output.out", "w", stdout);
#else
	// online submission
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
}

Compilation message

doktor.cpp: In function 'void io()':
doktor.cpp:68:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  freopen("input.in", "r", stdin);
  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
doktor.cpp:69:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  freopen("output.out", "w", stdout);
  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23952 KB Output is correct
2 Correct 23 ms 24028 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 24456 KB Output is correct
2 Correct 202 ms 30432 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 30432 KB Output is correct
2 Correct 76 ms 30432 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 396 ms 40152 KB Output is correct
2 Correct 304 ms 40152 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 234 ms 40152 KB Output is correct
2 Correct 274 ms 43532 KB Output is correct