제출 #42395

#제출 시각아이디문제언어결과실행 시간메모리
42395Aidyn_ALongest beautiful sequence (IZhO17_subsequence)C++14
0 / 100
4 ms504 KiB
#include <stdio.h> #include <bits/stdc++.h> #define pb push_back #define pf push_front #define pp pop_back #define sz(a) (int)(a.size()) #define mp make_pair #define F first #define S second #define next _next #define prev _prev #define left _left #define right _right #define y1 _y1 #define all(x) x.begin(), x.end() #define what_is(x) #x << " is " << (x) using namespace std; typedef long long ll; typedef unsigned long long ull; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int N = (int)1e6 + 123; const ll INF = (ll)1e18 + 123; const int inf = (int)1e9 + 123; const int MOD = (int)1e9 + 7; void megaRandom() { unsigned int FOR; asm("rdtsc" : "=A"(FOR)); srand(FOR); } int n, a[N], b[N]; int half = 2; pii dp[(1<<10) + 123][(1<<10) + 123][11]; int now[N], pr[N]; int main() { megaRandom(); scanf("%d", &n);//cin >> n; for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);//cin >> a[i]; for(int i = 1; i <= n; i ++) scanf("%d", &b[i]);//cin >> b[i]; int res = 0, res_p = -1; for(int i = 1; i <= n; i ++) { //GET int j = -1; for(int mask = 0; mask < (1 << half); mask ++) { int origin = (mask << half); int left = b[i] - __builtin_popcount(origin & a[i]); if(left >= 0) { int lasthalf = (a[i] & ((1 << half) - 1)); if(dp[mask][lasthalf][left].F + 1 > now[i]) { now[i] = dp[mask][lasthalf][left].F + 1; j = dp[mask][lasthalf][left].S; } } } pr[i] = j; assert(__builtin_popcount(a[i] & a[j]) == b[i]); //cout << "i: " << i << " now: " << now[i] << "\n"; //UPDATE for(int mask = 0; mask < (1 << half); mask ++) { int firsthalf = (a[i] >> half); int changed = __builtin_popcount(a[i] & mask); if(dp[firsthalf][mask][changed].F < now[i]) { dp[firsthalf][mask][changed] = {now[i], i}; } } if(now[i] > res) res = now[i], res_p = i; } printf("%d\n", res);//cout << res << "\n"; vector<int> v; while(res_p > 0) { v.pb(res_p); res_p = pr[res_p]; } reverse(all(v)); for(auto aa : v) printf("%d ", aa);//cout << aa << ' '; return 0; }

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

subsequence.cpp: In function 'int main()':
subsequence.cpp:45:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);//cin >> n;
                 ^
subsequence.cpp:47:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a[i]);//cin >> a[i];
                     ^
subsequence.cpp:49:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &b[i]);//cin >> b[i];
                     ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...