제출 #657242

#제출 시각아이디문제언어결과실행 시간메모리
657242RambaXGorilla전차 (CEOI13_tram)C++17
80 / 100
140 ms12120 KiB
#include<cstdio> #include<algorithm> #include<utility> #include<iterator> #include<vector> #include<set> #include<map> using namespace std; typedef long long ll; typedef pair <int,int> ii; typedef pair <ll, ii> lii; const int inf = 1000000000; int N, M; ii entries[30010]; set <lii> best; map <int,set <int>> rows; ll sq(ll a){ return a * a; } vector <lii> calc(int a, int b){ vector <lii> cands; for(int i = 0;i < 2;i++){ for(int j = 1;j < 3;j++){ cands.push_back(lii(sq(inf), ii(max(min((a + b) / 2 + i, N), 1), j))); } } int nums[] = {a, b}; for(int i = 0;i < 4;i++){ for(int j = 0;j < 2;j++){ for(int k : rows[nums[j]]){ cands[i].first = min(cands[i].first, sq(cands[i].second.first - nums[j]) + sq(cands[i].second.second - k)); } } } return cands; } void merge(int a, int b){ vector <lii> cands = calc(a, b); for(lii i : cands){ i.first *= -1; best.insert(i); } } void split(int a, int b){ vector <lii> cands = calc(a, b); for(lii i : cands){ i.first *= -1; best.erase(i); } } int main(){ rows[-inf]; rows[inf + 2]; best.insert(lii(-sq(inf), ii(1, 1))); scanf("%d %d\n",&N,&M); for(int i = 1;i < M + 1;i++){ char a; scanf("%c",&a); if(a == 'E'){ scanf("\n"); ii place = best.begin()->second; entries[i] = place; split((--rows.upper_bound(place.first))->first, rows.upper_bound(place.first)->first); split((--rows.lower_bound(place.first))->first, rows.lower_bound(place.first)->first); rows[place.first].insert(place.second); merge((--rows.upper_bound(place.first))->first, rows.upper_bound(place.first)->first); merge((--rows.lower_bound(place.first))->first, rows.lower_bound(place.first)->first); printf("%d %d\n",place.first,place.second); } else{ int b; scanf(" %d\n",&b); ii place = entries[b]; split((--rows.upper_bound(place.first))->first, rows.upper_bound(place.first)->first); split((--rows.lower_bound(place.first))->first, rows.lower_bound(place.first)->first); rows[place.first].erase(place.second); if(rows[place.first].empty()){ rows.erase(place.first); } merge((--rows.upper_bound(place.first))->first, rows.upper_bound(place.first)->first); merge((--rows.lower_bound(place.first))->first, rows.lower_bound(place.first)->first); } } }

컴파일 시 표준 에러 (stderr) 메시지

tram.cpp: In function 'int main()':
tram.cpp:55:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |     scanf("%d %d\n",&N,&M);
      |     ~~~~~^~~~~~~~~~~~~~~~~
tram.cpp:58:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |         scanf("%c",&a);
      |         ~~~~~^~~~~~~~~
tram.cpp:60:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |             scanf("\n");
      |             ~~~~~^~~~~~
tram.cpp:72:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |             scanf(" %d\n",&b);
      |             ~~~~~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...