2018年日本情報オリンピック予選の四番「日本沈没」の小課題3を、競技終了後の今、解説をヒントに実装してみたのですが、常に2パターンのテストデータでRE(実行時エラー)とWA(不正解)が出ます。いろいろとコードをいじっては見たのですが一向に変化がありません。どこが不正解&実行時エラーを誘発しているのでしょうか?ご教授頂けると幸いです。
2018JOI 4番:
日本列島は細長い列島である.日本列島は平行な境界線により N 個の区画に分けられている.区画には端から順に 1 から N の番号が付けられている.区画 i (1 ≦ i ≦ N) の高さは A_i である.
日本列島は海に囲まれており,海面の高さは場所によらず一定である.高さが海面の高さより高い区画を陸地と呼ぶ.
陸地が連続している部分のことを島と呼ぶ.より正確に書くと以下の通りである.整数 l, r (1 ≦ l ≦ r ≦ N) について,日本列島のうち区画 l,区画 l+1,...,区画 r からなる部分を領域 [l, r] という.以下の条件を満たす領域 [l, r] を島という:
区画 l,区画 l+1,...,区画 r はすべて陸地である.
l>1 ならば区画 l-1 は陸地ではない.
r ならば区画 r+1 は陸地ではない.
海面の上昇により,日本列島は少しずつ沈没している.現在の海面の高さは 0 であるが,これは時間が経つにつれて徐々に上がり,ついには日本全体が海になってしまう.JOI 君は,海面の高さが上昇すると,日本の島の数が増減することに気付いた.現在から,日本に陸地がなくなるまでの間 (現在も含む) における,島の数の最大値を求めたい.
制約
1 ≦ N ≦ 100000 (= 10^5)
0 ≦ A_i ≦ 1000000000 (= 10^9) (1 ≦ i ≦ N)
入力・出力
入力
入力は以下の形式で標準入力から与えられる.
N
A_1 A_2 ... A_N出力
現在から,日本に陸地がなくなるまでの間 (現在も含む) における,島の数の最大値を 1 行で出力せよ.
問題のあるコード:
消える陸地とその左右の二つの区画の高低で増減を判定しています。
C++
1#include <iostream> 2#include <map> 3#include <vector> 4#include <algorithm> 5 6using namespace std; 7 8int main(void){ 9 long long N, Ap[100005]; 10 pair<long long, long long> a; 11 vector<pair<long long, long long> > A; 12 cin >> N; 13 for(long long i = 0; i < N; i++){ 14 cin >> a.first; 15 Ap[i] = a.first; 16 a.second = i; 17 A.push_back(a); 18 } 19 stable_sort(A.begin(), A.end()); 20 long long mam = 1, latest = 1; 21 for(long long i = 0; i < N;){ 22 long long sealevel = A[i].first; 23 while(A[i].first == sealevel){ 24 long long begin = A[i].second; 25 //cout << "smalnum: " << i << " leftnum: " << begin << " sealevel: " << sealevel << endl; 26 while((A[i].second + 1 == A[i+1].second) && (A[i].first == A[i+1].first) && (i < N - 1)){ 27 i++; 28 } 29 long long end = A[i].second; 30 //cout << "begin: " << begin << " end: " << end << " N: " << N << endl; 31 if((begin == 0 && Ap[end+1] < sealevel) || (end == N-1 && Ap[begin-1] < sealevel) || (begin == 0 && end == N-1)){ 32 latest--; //cout << "decrease at the end: " << i << endl; 33 } else if(begin == 0 || end == N-1){ 34 //cout << "at the end -> break" << endl; 35 } else if(Ap[end+1] < sealevel && Ap[begin-1] < sealevel){ 36 latest--; //cout << "decrease in middle: " << i << endl; 37 } else if(Ap[end+1] > sealevel && Ap[begin-1] > sealevel){ 38 latest++; //cout << "increase: " << i << endl; 39 } 40 i++; 41 } 42 mam = max(mam, latest); 43 //cout << "sealevel: " << sealevel << " latest: " << latest << " maximum so far: " << mam << endl; 44 } 45 cout << mam << endl; 46 // for(long long i = 0; i < N; i++){ 47 // cout << A[i].first << " " << A[i].second << endl; 48 // } 49 return 0; 50}
あなたの回答
tips
プレビュー