제출 #828274

#제출 시각아이디문제언어결과실행 시간메모리
828274caganyanmazPaint By Numbers (IOI16_paint)C++14
59 / 100
1 ms312 KiB
#include <bits/stdc++.h> #include "paint.h" #ifdef DEBUGGING #include "../debug.h" #else #define debug(x...) void(42) #endif using namespace std; constexpr static int INF = 1e9; struct SegTree { vector<int> v; int n; SegTree(int n) : n(n), v(n*2, INF) {} void build(const vector<int>& r) { for (int i = n; i < 2*n; i++) v[i] = r[i-n]; for (int i = n-1; i > 0; i--) v[i] = min(v[i<<1], v[(i<<1)|1]); } int get(int l, int r) { int res = INF; for (l+=n,r+=n;l<r;l>>=1,r>>=1) { if (l&1) res = min(res, v[l++]); if (r&1) res = min(res, v[--r]); } return res; } }; #include <cstdlib> string solve_puzzle(string s, vector<int> c) { vector<int> l(s.size()), r(s.size()); SegTree st(c.size()); st.build(c); int cc = 0; int cl = 0; for (int i = 0; i < s.size(); i++) { if (cc == c.size()) { l[i] = c.size()*2; continue; } if (i - cl == c[cc]) { for (int j = cl; j < i; j++) l[j] = cc*2+1; cc++; l[i] = cc*2; cl = i+1; } else if (s[i] == '_') { while (cl <= i) l[cl++] = cc*2; } } if (cc < c.size()) { for (int j = cl; j < s.size(); j++) l[j] = cc*2+1; } cc = c.size()-1; int cr = s.size(); for (int i = s.size()-1; i >= 0; i--) { debug(i, cr, cc); if (cc < 0) { r[i] = 0; continue; } if (s[i] == '_') { while (cr > i) r[--cr] = (cc+1) * 2; } else if (cr - i == c[cc]) { for (int j = i; j < cr; j++) r[j] = cc*2+1; cc--; if (i > 0) r[i-1] = (cc+1)*2; cr = i-1; i--; } } vector<int> nlw(s.size()); vector<int> nrw(s.size()); int last = -1; for (int i = 0; i < s.size(); i++) { if (s[i] == '_') last = i; nlw[i] = last; } last = s.size(); for (int i = s.size()-1; i >= 0; i--) { if (s[i] == '_') last = i; nrw[i] = last; } string res(s.size(), '?'); for (int i = 0; i < s.size(); i++) { if (l[i] != r[i]) { int diff = nrw[i] - nlw[i]; if (l[i]&1 != r[i]&1) continue; debug(i, nlw[i], nrw[i], diff, r[i]/2, l[i]/2, st.get(r[i]/2, l[i]/2)); if (diff < st.get(r[i]/2, l[i]/2)) res[i] = '_'; } else if (l[i]&1) res[i] = 'X'; else res[i] = '_'; } debug(l,r); return res; }

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

paint.cpp: In constructor 'SegTree::SegTree(int)':
paint.cpp:17:6: warning: 'SegTree::n' will be initialized after [-Wreorder]
   17 |  int n;
      |      ^
paint.cpp:16:14: warning:   'std::vector<int> SegTree::v' [-Wreorder]
   16 |  vector<int> v;
      |              ^
paint.cpp:18:2: warning:   when initialized here [-Wreorder]
   18 |  SegTree(int n) : n(n), v(n*2, INF) {}
      |  ^~~~~~~
paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:44:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |  for (int i = 0; i < s.size(); i++)
      |                  ~~^~~~~~~~~~
paint.cpp:46:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |   if (cc == c.size())
      |       ~~~^~~~~~~~~~~
paint.cpp:66:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |  if (cc < c.size())
      |      ~~~^~~~~~~~~~
paint.cpp:68:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |   for (int j = cl; j < s.size(); j++)
      |                    ~~^~~~~~~~~~
paint.cpp:100:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |  for (int i = 0; i < s.size(); i++)
      |                  ~~^~~~~~~~~~
paint.cpp:114:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |  for (int i = 0; i < s.size(); i++)
      |                  ~~^~~~~~~~~~
paint.cpp:119:15: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
  119 |    if (l[i]&1 != r[i]&1)
#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...