Submission #83635

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
83635	2018-11-09T14:07:33 Z	wjoao	Kralj (COCI16_kralj)	C++11	140 / 140	804 ms	43436 KB

kralj

#include<bits/stdc++.h>
#define maxn 500010
using namespace std;

int n, dwarves[maxn], a, elves[maxn], sobras[maxn];
vector<int> f[maxn];

int main(){
  scanf(" %d", &n);
  for(int i = 1; i <= n; i++){
    scanf(" %d", &a);
    f[a].push_back(i);
  }

  for(int i = 1; i <= n; i++) scanf(" %d", &dwarves[i]);

  for(int i = 1; i <= n; i++) scanf(" %d", &elves[i]);

  for(int k = 0, j = 1, sobra = 0; k < 3*n; k++, j++, sobra--){
    if( j == n+1 ) j = 1;
    sobra = max(0, sobra);
    sobras[j] = max(sobra, sobras[j]);
    sobra += f[j].size();
  }

  int start_point;
  for(int i = 1; i <= n; i++){
    if(sobras[i] == 0){
      start_point = i;
      break;
    }
  }

  int vitorias = 0;
  int j = start_point;
  set<int> pokemon;
  while(true){
    for(int k = 0; k < f[j].size(); k++){
      pokemon.insert(elves[f[j][k]]);
    }
    set<int>::iterator it = pokemon.upper_bound(dwarves[j]);
    if(it == pokemon.end()){
      it = pokemon.begin();
    }
    if( *it > dwarves[j]) {
      vitorias++;
    }
    pokemon.erase(it);
    j++;
    if( j == n+1 ) j = 1;
    if( j == start_point ) break;
  }


  printf("%d\n", vitorias);
  return 0;
}

Compilation message

kralj.cpp: In function 'int main()':
kralj.cpp:38:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int k = 0; k < f[j].size(); k++){
                    ~~^~~~~~~~~~~~~
kralj.cpp:9:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %d", &n);
   ~~~~~^~~~~~~~~~~
kralj.cpp:11:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf(" %d", &a);
     ~~~~~^~~~~~~~~~~
kralj.cpp:15:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   for(int i = 1; i <= n; i++) scanf(" %d", &dwarves[i]);
                               ~~~~~^~~~~~~~~~~~~~~~~~~~
kralj.cpp:17:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   for(int i = 1; i <= n; i++) scanf(" %d", &elves[i]);
                               ~~~~~^~~~~~~~~~~~~~~~~~
kralj.cpp:51:5: warning: 'start_point' may be used uninitialized in this function [-Wmaybe-uninitialized]
     if( j == start_point ) break;
     ^~

Subtask #1

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	758 ms	37220 KB	Output is correct
2	Correct	549 ms	37220 KB	Output is correct
3	Correct	804 ms	42676 KB	Output is correct
4	Correct	687 ms	43436 KB	Output is correct
5	Correct	499 ms	43436 KB	Output is correct
6	Correct	429 ms	43436 KB	Output is correct
7	Correct	555 ms	43436 KB	Output is correct
8	Correct	501 ms	43436 KB	Output is correct
9	Correct	577 ms	43436 KB	Output is correct
10	Correct	516 ms	43436 KB	Output is correct