Submission #780627

#TimeUsernameProblemLanguageResultExecution timeMemory
78062779brueTram (CEOI13_tram)C++17
0 / 100
27 ms6404 KiB
#include <bits/stdc++.h> #define PAIR(x,y) ((x)*2+(y)) using namespace std; typedef long long ll; int n, q; struct Info{ int l, r, ss, es; /// ss: l-1 상태, es: r+1 상태 int PR; Info(){} Info(int l, int r, int ss, int es): l(l), r(r), ss(ss), es(es){ if(l==1 && r==n) PR = 1e9; else if(l==1 || r==n) PR = (ss|es)==3 ? PAIR(r-l+1, 0) : PAIR(r-l+1, 1); else if((ss|es)==3) PR = PAIR((r-l)/2+1, (r-l)%2); else PR = PAIR((r-l)/2+1, 1); } bool operator<(const Info &nxt)const{ if(PR != nxt.PR) return PR > nxt.PR; return l<nxt.l; } }; int arr[150002][2]; int qx[30002], qy[30002]; set<Info> st; /// 행과 행 사이의 틈 관리 set<pair<int, int> > interval; /// st에서 (l, r)만 관리 set<pair<int, int> > blank; /// 한 열만 사람이 탄 행을 관리 int calc(int x){ return arr[x][0]+arr[x][1]*2; } int findLoc(Info p){ int l = p.l, r = p.r, ss=p.ss, es=p.es; if(l==1 && r==n) return PAIR(1, 0); else if(l==1 || r==n) return PAIR(l==1 ? 1 : n, (ss|es)==1 ? 1 : 0); else if(es==3) return PAIR((l+r)/2, ss==1 ? 1 : 0); else if(ss==3) return PAIR((l+r+1)/2, es==1 ? 1 : 0); else if(ss==es) return PAIR((l+r)/2, ss==1 ? 1 : 0); else return PAIR((l+r)/2, (ss==1 && (r-l)%2) ? 1 : 0); } void put(int idx){ ll PR1 = st.empty() ? -1 : st.begin()->PR; int p1 = st.empty() ? INT_MAX : findLoc(*st.begin()); ll PR2 = blank.empty() ? -1 : 2; int p2 = blank.empty() ? INT_MAX : PAIR(blank.begin()->first, blank.begin()->second); int loc = (PR1 > PR2) ? p1 : (PR1 < PR2) ? p2 : min(p1, p2); int x = loc/2, y = loc%2; arr[x][y] = 1; qx[idx] = x, qy[idx] = y; printf("%d %d\n", x, y+1); /// blank 갱신 if(arr[x][!y] == 1){ blank.erase(make_pair(x, y)); return; } else{ blank.insert(make_pair(x, !y)); } /// st 갱신 Info tmp = *st.begin(); st.erase(st.begin()); interval.erase(make_pair(tmp.l, tmp.r)); if(tmp.l != x){ st.insert(Info(tmp.l, x-1, calc(tmp.l-1), calc(x))); interval.insert(make_pair(tmp.l, x-1)); } if(tmp.r != x){ st.insert(Info(x+1, tmp.r, calc(x), calc(tmp.r+1))); interval.insert(make_pair(x+1, tmp.r)); } } void erase(int x, int y){ if(arr[x][!y]){ blank.insert(make_pair(x, y)); arr[x][y] = 0; return; } else{ blank.erase(make_pair(x, !y)); } int l = x, r = x; auto it = interval.lower_bound(make_pair(x, 0)); if(it != interval.begin() && prev(it)->second == x-1){ l = prev(it)->first; st.erase(Info(prev(it)->first, prev(it)->second, calc(prev(it)->first-1), calc(prev(it)->second+1))); interval.erase(prev(it)); } if(it != interval.end() && it->first == x+1){ r = it->second; st.erase(Info(it->first, it->second, calc(it->first-1), calc(it->second+1))); interval.erase(it); } arr[x][y] = 0; interval.insert(make_pair(l, r)); st.insert(Info(l, r, calc(l-1), calc(r+1))); } int main(){ scanf("%d %d", &n, &q); st.insert(Info(1, n, 0, 0)); for(int i=1; i<=q; i++){ char c; scanf(" %c", &c); if(c=='E') put(i); else{ int x; scanf("%d", &x); erase(qx[x], qy[x]); } // printf("After query %d\n", i); // for(auto p: interval) printf("[%d, %d] ", p.first, p.second); puts(""); // for(Info p: st) printf("[%d, %d] (%d %d), ", p.l, p.r, p.ss, p.es); puts(""); } }

Compilation message (stderr)

tram.cpp: In function 'int main()':
tram.cpp:113:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  113 |     scanf("%d %d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~
tram.cpp:117:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  117 |         scanf(" %c", &c);
      |         ~~~~~^~~~~~~~~~~
tram.cpp:121:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  121 |             scanf("%d", &x);
      |             ~~~~~^~~~~~~~~~
#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...