답안 #83635

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
83635 2018-11-09T14:07:33 Z wjoao Kralj (COCI16_kralj) C++11
140 / 140
804 ms 43436 KB
#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;
     ^~
# 결과 실행 시간 메모리 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