oj.uz

Submission #82193

# Submission time Handle Problem Language Result Execution time Memory
82193 2018-10-29T13:12:41 Z wjoao Doktor (COCI17_doktor) C++11
100 / 100
 273 ms 49200 KB 
#include<bits/stdc++.h>
#define maxn 500100
using namespace std;

int n;
vector<int> v[2*maxn];
int entrada[2*maxn], prefix[2*maxn];

int query(int a, int b){
  return prefix[b]-prefix[a-1];
}

int main(){
  scanf("%d", &n);
  for(int i = 1; i <= n; i++){
    scanf(" %d", &entrada[i*2]);
    entrada[i*2] = entrada[i*2]*2;
  }

  //for(int i = 1; i <= 2*n; i++){
  //  cout << i << " - " << entrada[i] << endl;
 // }

  for(int i = 1; i <= n; i++){
    if(i*2 == entrada[i*2]) {
      prefix[i*2] = 1;
      continue;
    }

    int middle = ( entrada[i*2] + i*2 ) / 2;
   // cout << "Novo middle: " << middle << " Valor: " << entrada[i*2] << endl;
    v[middle].push_back(abs(middle-i*2));
  }

  //cout << "X" << endl;

  for(int i = 1; i < 2*maxn; i++) prefix[i] += prefix[i-1];

  
  //for(int i = 1; i <= 2*n; i++){
 //   cout << i << " prefix - " << prefix[i] << endl;
  //}
  int res = 0;
  int A = 2;
  int B = 2;
  for(int i = 2; i < 2*maxn; i++){
    sort(v[i].begin(), v[i].end());
    for(int j = 0; j < v[i].size(); j++){
      int valor = v[i][j];
      int atual = 
      j 
      - query(i-valor, i+valor)
      + ( (i%2 == 0 && i == entrada[i] ) ? 1 : 0 );

      if(atual > res){
        res = atual;
        A = i-valor;
        B = i+valor;
      }
    }
  }

  printf("%d %d\n", entrada[A]/2, entrada[B]/2);


  return 0;
}

Compilation message

doktor.cpp: In function 'int main()':
doktor.cpp:48:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j = 0; j < v[i].size(); j++){
                    ~~^~~~~~~~~~~~~
doktor.cpp:14:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &n);
   ~~~~~^~~~~~~~~~
doktor.cpp:16:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf(" %d", &entrada[i*2]);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 27768 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 27892 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 27892 KB Output is correct
2 Correct 31 ms 27988 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 27988 KB Output is correct
2 Correct 32 ms 28024 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 28024 KB Output is correct
2 Correct 33 ms 28032 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 28092 KB Output is correct
2 Correct 35 ms 28092 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 28260 KB Output is correct
2 Correct 108 ms 33584 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 33584 KB Output is correct
2 Correct 64 ms 33584 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 273 ms 49200 KB Output is correct
2 Correct 188 ms 49200 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 49200 KB Output is correct
2 Correct 99 ms 49200 KB Output is correct