Submission #82193

#	Time	Username	Problem	Language	Result	Execution time	Memory
82193		wjoao	Doktor (COCI17_doktor)	C++11	100 / 100	273 ms	49200 KiB

doktor

#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 (stderr)

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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10