제출 #139862

#제출 시각아이디문제언어결과실행 시간메모리
139862SirCenessAliens (IOI16_aliens)C++14
0 / 100
2 ms380 KiB
#include "aliens.h" #include <bits/stdc++.h> #define x first #define y second #define pb push_back #define mp make_pair #define inside sl<=l&&r<=sr #define outside r<sl||sr<l #define orta ((l+r)>>1) #define INF 1000000000000009 #define mod 1000000007 #define ppair(x) "(" << x.first << ", " << x.second << ") " #define bas(x) #x << ": " << x << " " #define prarr(x, n); cerr << #x << ": "; for(int qsd = 0; qsd < n; qsd++) cerr << x[qsd] << " "; cerr << "\n"; #define prarrv(x); cerr << #x << ": "; for(int qsd = 0; qsd < (int)x.size(); qsd++) cerr << x[qsd] << " "; cerr << "\n"; using namespace std; typedef long long ll; vector<pair<int, int> > arr; ll sq(int a, int b){ if (a < b) return 0; return (ll)(a-b+1)*(ll)(a-b+1); } ll getcost(int a, int b){ return sq(arr[b].x, arr[a].y) - sq(arr[a].x, arr[a].y) - sq(arr[b].x, arr[b].y) + sq(arr[a].x, arr[b].y); } ll take_photos(int n, int m, int k, vector<int> r, vector<int> c){ vector<pair<int, int> > ekle1; for (int i = 0; i < n; i++) if (r[i] >= c[i]) ekle1.pb(mp(r[i], c[i])); else ekle1.pb(mp(c[i], r[i])); sort(ekle1.begin(), ekle1.end()); for (int i = 0; i < n-1; i++){ if (arr.size() != 0 && arr.back().first == ekle1[i].first) continue; if (ekle1[i].second != ekle1[i+1].second) arr.pb(ekle1[i]); } if (arr.size() == 0 || arr.back().first != ekle1[n-1].first) arr.pb(ekle1[n-1]); //for (int i = 0; i < arr.size(); i++) cout << ppair(arr[i]) << endl; ll ans = 0; for (int i = 0; i < arr.size(); i++){ ans += sq(arr[i].x, arr[i].y); if (i+1 != arr.size()) ans -= sq(arr[i].x, arr[i+1].y); } set<pair<ll, int> > st; for (int i = 0; i < arr.size()-1; i++){ ll cost = getcost(i, i+1); st.insert(mp(cost, i)); } vector<int> bef(arr.size()); for (int i = 1; i < arr.size(); i++) bef[i] = i-1; bef[0] = -1; vector<int> nex(arr.size()); for (int i = 0; i < arr.size()-1; i++) nex[i] = i+1; nex[arr.size()-1] = -1; for (int q = 0; q < (int)arr.size()-k; q++){ //for (pair<ll, int> eleman: st) cout << ppair(eleman) << " "; cout << endl; int i = st.begin() -> second; ans += st.begin() -> first; int b = bef[i]; int nx = nex[nex[i]]; st.erase(st.begin()); if (b != -1){ ll costb = getcost(b, i); int tmp = st.size(); st.erase(st.find(mp(costb, b))); if (tmp-1 != st.size()) assert(0); } if (nx != -1){ ll costn = getcost(nex[i], nx); int tmp = st.size(); st.erase(st.find(mp(costn, nex[i]))); if (tmp-1 != st.size()) assert(0); } arr[i].x = arr[nex[i]].x; nex[i] = nx; if (nx != -1) bef[nx] = i; if (b != -1) st.insert(mp(getcost(b, i), b)); if (nx != -1) st.insert(mp(getcost(i, nx), i)); } return ans; }

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

aliens.cpp: In function 'll take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:46:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < arr.size(); i++){
                  ~~^~~~~~~~~~~~
aliens.cpp:48:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (i+1 != arr.size()) ans -= sq(arr[i].x, arr[i+1].y);
       ~~~~^~~~~~~~~~~~~
aliens.cpp:52:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < arr.size()-1; i++){
                  ~~^~~~~~~~~~~~~~
aliens.cpp:58:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i < arr.size(); i++) bef[i] = i-1;
                  ~~^~~~~~~~~~~~
aliens.cpp:61:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < arr.size()-1; i++) nex[i] = i+1;
                  ~~^~~~~~~~~~~~~~
aliens.cpp:76:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (tmp-1 != st.size()) assert(0);
        ~~~~~~^~~~~~~~~~~~
aliens.cpp:82:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (tmp-1 != st.size()) assert(0);
        ~~~~~~^~~~~~~~~~~~
#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...