제출 #464570

#제출 시각아이디문제언어결과실행 시간메모리
464570BungmintLongest beautiful sequence (IZhO17_subsequence)C++17
100 / 100
4303 ms166780 KiB
#pragma GCC optimize("O3") #pragma GCC target("sse4") #include <bits/stdc++.h> using namespace std; using ll = long long; using vi = vector<int>; using pii = pair<int, int>; using vpi = vector<pii>; using pll = pair<ll, ll>; using vl = vector<ll>; using vpl = vector<pll>; using ld = long double; #define all(v) (v).begin(), (v).end() #define ar array #define pb push_back #define sz(x) (int)(x).size() #define fi first #define se second #define lb lower_bound #define ub upper_bound #define FOR(i, a, b) for (int i = (a); i < (b); ++i) #define F0R(i, a) FOR(i, 0, a) #define ROF(i, a, b) for (int i = (b)-1; i >= (a); --i) #define R0F(i, a) ROF(i, 0, a) #define REP(a) F0R(_, a) const int INF = 1e9; const ll LINF = 1e18; const int MOD = 1e9 + 7; //998244353; const ld PI = acos((ld)-1.0); const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1}; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); template <typename T> using pqg = priority_queue<T, vector<T>, greater<T>>; template <typename T> bool ckmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; } template <typename T> bool ckmax(T &a, const T &b) { return b > a ? a = b, 1 : 0; } template <typename A, typename B> ostream &operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; } template <typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream &operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; } void dbg_out() { cerr << endl; } template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); } #ifdef LOCAL #define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__) #else #define dbg(...) #endif struct chash { static uint64_t splitmix64(uint64_t x) { x += 0x9e3779b97f4a7c15; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9; x = (x ^ (x >> 27)) * 0x94d049bb133111eb; return x ^ (x >> 31); } size_t operator()(uint64_t x) const { static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count(); return splitmix64(x + FIXED_RANDOM); } size_t operator()(pair<uint64_t,uint64_t> x) const { static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count(); return splitmix64(x.first + FIXED_RANDOM)^(splitmix64(x.second + FIXED_RANDOM) >> 1); } }; void setIO(string s) { freopen((s + ".in").c_str(), "r", stdin); freopen((s + ".out").c_str(), "w", stdout); } #define left awehfulawefhuil #define right rhuewiafaiuewhfaiuewhf void solve() { int n; cin >> n; vi a(n+1), k(n+1); vi par(n+1); FOR(i, 1, n+1) cin >> a[i]; FOR(i, 1, n+1) cin >> k[i]; static pii dp[1<<10][1<<10][20]; int last=-1, m = -1; FOR(i, 1, n+1){ int left = a[i]&((1<<10)-1), right = a[i]>>10, opt = 0; F0R(mask, 1<<10){ int x = k[i]-__builtin_popcount(left&mask); if (x>=0&&x<=10&&ckmax(opt, dp[mask][right][x].fi)){ par[i] = dp[mask][right][x].se; } } F0R(mask, 1<<10){ int x = __builtin_popcount(right&mask); ckmax(dp[left][mask][x], pii(opt+1, i)); } if (ckmax(m, opt+1)) last = i; } vi ans; while(last){ ans.pb(last); last = par[last]; } assert(sz(ans)==m); reverse(all(ans)); cout << m << endl; F0R(j, m) cout << ans[j]<<"\n "[j+1<m]; } int main() { cin.tie(0)->sync_with_stdio(0); cin.exceptions(cin.failbit); int testcase=1; // cin >> testcase; while (testcase--) { solve(); } }

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

subsequence.cpp: In function 'void setIO(std::string)':
subsequence.cpp:95:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
subsequence.cpp:96:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |     freopen((s + ".out").c_str(), "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...