제출 #1062438

#제출 시각아이디문제언어결과실행 시간메모리
1062438seoul_koreaNaval battle (CEOI24_battle)C++17
76 / 100
679 ms51668 KiB
// Goten2308 #include<bits/stdc++.h> using namespace std; #define int long long using ll = long long; using ii = pair <int, int>; #define fi first #define se second #define mp(x, y) make_pair(x, y) #define pb(x) push_back(x) #define all(x) (x).begin(), (x).end() #define endl '\n' #define BIT(x, y) ((x >> y) & 1) #define MASK(x) (1 << x) #define MOD 1000000007 #define MULTI_TEST1 #define __GOTEN_WILL_BE_BETTER__ signed main() template <class T> bool maximize(T& a, T b) { if(a < b) { a = b; return true; } return false; } template <class T> bool minimize(T& a, T b) { if(a > b) { a = b; return true; } return false; } template <class T> void add(T& a, T b) { a += b; if(a >= MOD) a -= MOD; } template <class T> void sub(T& a, T b) { a -= b; if(a < 0) a += MOD; } const int maxN = (int)2e5 + 7; int n; struct Event{ int fr, to, at; Event() { fr = 0, to = 0, at = 0; } Event(int _fr, int _to, int _at) { fr = _fr; to = _to; at = _at; } }; bool cmp(Event a, Event b) { return a.at < b.at; } struct Board{ int x, y; char type; } a[maxN]; vector<int> store[5]; namespace Subtask5 { bool Check() { return n <= 5000; } map<ii, bool> isDelTime; // int n; int enc(char x) { if(x == 'S') return 0; if(x == 'N') return 1; if(x == 'E') return 2; if(x == 'W') return 3; } int calcTime(Board a, Board b) { if(enc(a.type) > enc(b.type)) swap(a, b); if(enc(a.type) == 0) { if(enc(b.type) == 1) { if(a.x > b.x || a.y != b.y || (a.x + b.x & 1)) return -1; return (a.x + b.x >> 1) - a.x; } if(enc(b.type) == 2) { if(b.x - a.x == a.y - b.y && a.y - b.y >= 0) return a.y - b.y; return -1; } if(enc(b.type) == 3) { if(b.x - a.x == b.y - a.y && b.y - a.y >= 0) return b.y - a.y; return -1; } } if(enc(a.type) == 1) { if(enc(b.type) == 2) { if(a.x - b.x == a.y - b.y && a.y - b.y >= 0) return a.y - b.y; return -1; } if(enc(b.type) == 3) { if(a.x - b.x == b.y - a.y && b.y - a.y >= 0) return b.y - a.y; return -1; } } if(enc(a.type) == 2) { if(enc(b.type) == 3) { if((a.y + b.y & 1) || a.x != b.x || a.y > b.y) return -1; return (a.y + b.y >> 1) - a.y; } } } void solve() { for(int i = 1; i <= n; i++) { cin >> a[i].y >> a[i].x >> a[i].type; store[enc(a[i].type)].pb(i); } vector<Event> timeline; for(int i = 1; i <= n; i++) { for(int nxt = 0; nxt <= 3; nxt++) { if(nxt == enc(a[i].type)) continue; for(auto j : store[nxt]) { if(i > j) continue; int k = calcTime(a[i], a[j]); if(k == -1) continue; timeline.push_back(Event(i, j, k)); } } } sort(all(timeline), cmp); vector<bool> isAlive(n + 1, 1); Event last = Event(); for(auto sukien : timeline) { if(isAlive[sukien.fr] && isAlive[sukien.to] || isDelTime.find(mp(sukien.fr, sukien.at)) != isDelTime.end() || isDelTime.find(mp(sukien.to, sukien.at)) != isDelTime.end()) { isAlive[sukien.fr] = 0; isAlive[sukien.to] = 0; // isDelTime[sukien.fr][sukien.at] = 1; isDelTime[mp(sukien.fr,sukien.at)] = 1; isDelTime[mp(sukien.to,sukien.at)] = 1; } // last = sukien; // cout << sukien.fr << ' ' << sukien.to << ' ' << sukien.at << endl; } for(int i = 1; i <= n; i++) if(isAlive[i]) cout << i << endl; } } namespace Subtask6 { void solve() { for(int i = 1; i <= n; i++) cin >> a[i].y >> a[i].x >> a[i].type; vector<ii> canDie; for(int i = 1; i <= n; i++) { canDie.push_back(mp(a[i].x + a[i].y, i)); } sort(all(canDie)); vector<bool> isAlive(n + 1, true); for(int timeTry = 0; timeTry < canDie.size();) { vector<ii> timeDie; int i = timeTry; for(; i < canDie.size(); i++) { if(canDie[i].fi != canDie[timeTry].fi) break; timeDie.push_back(mp(a[canDie[i].se].y, canDie[i].se)); } timeTry = i; sort(all(timeDie)); stack<int> st; for(auto x : timeDie) { if(a[x.se].type == 'S') { if(st.size()) { isAlive[x.se] = isAlive[st.top()] = 0; st.pop(); } }else st.push(x.se); } } for(int i = 1; i <= n; i++) if(isAlive[i]) cout << i << endl; } } void solve() { cin >> n; if(Subtask5::Check()) Subtask5::solve(); else Subtask6::solve(); } __GOTEN_WILL_BE_BETTER__ { #define task "" if(fopen(task".inp", "r")){ freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout); } if(fopen("task.inp", "r")){ freopen("task.inp", "r", stdin); freopen("task.out", "w", stdout); } cin.tie(0)->ios_base::sync_with_stdio(0); int nTest = 1; #ifdef MULTI_TEST cin >> nTest; #endif while(nTest--) { solve(); } cout << endl; return 0; }

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

Main.cpp: In function 'long long int Subtask5::calcTime(Board, Board)':
Main.cpp:68:52: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
   68 |                 if(a.x > b.x || a.y != b.y || (a.x + b.x & 1)) return -1;
      |                                                ~~~~^~~~~
Main.cpp:69:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   69 |                 return (a.x + b.x >> 1) - a.x;
      |                         ~~~~^~~~~
Main.cpp:92:25: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
   92 |                 if((a.y + b.y & 1) || a.x != b.x || a.y > b.y) return -1;
      |                     ~~~~^~~~~
Main.cpp:93:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   93 |                 return (a.y + b.y >> 1) - a.y;
      |                         ~~~~^~~~~
Main.cpp: In function 'void Subtask5::solve()':
Main.cpp:119:35: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  119 |             if(isAlive[sukien.fr] && isAlive[sukien.to] || isDelTime.find(mp(sukien.fr, sukien.at)) != isDelTime.end() || isDelTime.find(mp(sukien.to, sukien.at)) != isDelTime.end()) {
      |                ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
Main.cpp:117:15: warning: variable 'last' set but not used [-Wunused-but-set-variable]
  117 |         Event last = Event();
      |               ^~~~
Main.cpp: In function 'void Subtask6::solve()':
Main.cpp:142:38: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |         for(int timeTry = 0; timeTry < canDie.size();) {
      |                              ~~~~~~~~^~~~~~~~~~~~~~~
Main.cpp:145:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  145 |             for(; i < canDie.size(); i++) {
      |                   ~~^~~~~~~~~~~~~~~
Main.cpp: In function 'long long int Subtask5::enc(char)':
Main.cpp:62:5: warning: control reaches end of non-void function [-Wreturn-type]
   62 |     }
      |     ^
Main.cpp: In function 'long long int Subtask5::calcTime(Board, Board)':
Main.cpp:96:5: warning: control reaches end of non-void function [-Wreturn-type]
   96 |     }
      |     ^
Main.cpp: In function 'int main()':
Main.cpp:174:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  174 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:175:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  175 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:178:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  178 |         freopen("task.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:179:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  179 |         freopen("task.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#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...