제출 #1045551

#제출 시각아이디문제언어결과실행 시간메모리
1045551MinbaevXylophone (JOI18_xylophone)C++17
0 / 100
0 ms344 KiB
#include <bits/stdc++.h> #include "xylophone.h" #include <ext/pb_ds/assoc_container.hpp> #pragma GCC target("avx,avx2,fma") #pragma GCC optimize("Ofast,unroll-loops") using namespace std; using namespace __gnu_pbds; #define pb push_back #define all(x) x.begin(),x.end() #define rall(x) x.rbegin(),x.rend() #define f first #define s second //~ #define int long long #define ll long long #define pii pair<int,int> #define ar array template<class T>bool umax(T &a,T b){if(a<b){a=b;return true;}return false;} template<class T>bool umin(T &a,T b){if(b<a){a=b;return true;}return false;} typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; const int inf = 1e17 + 7; const int mod = 1e9 + 7; const int N = 3e5 + 5; const int md = 998244353; int binpow(int a, int b){ if(b == 0)return 1; if(b % 2 == 0){ int c = binpow(a,b/2); return (c*c)%mod; } return (binpow(a,b-1)*a)%mod; } int divi(int a, int b){ return (a*(binpow(b,mod-2)))%mod; } int n,m,k; void solve(int n){ vector<int>v(n+1); //~ for(int i = 1;i<n;i++){ //~ v[i] = quer //~ } int l = 2, r = n, pos = n; while(l <= r){ int mid = (l+r) / 2; int h = query(1,mid); //~ cout << 1 << " " << mid << endl; //~ int h; //~ cin >> h; if(h == n-1){ pos = mid; r = mid - 1; } else l = mid + 1; } //~ cout << pos << "\n"; vector<int>ans(n+1), vis(n+1); ans[pos] = n; vis[n] = 1; int h, u; h = query(pos - 1, pos); //~ cout << pos - 1 << " " << pos << endl; //~ cin >> h; ans[pos - 1] = n - h; vis[n - h] = 1; v[pos - 1] = h; if(pos < n){ h = query(pos, pos + 1); //~ cout << pos << " " << pos + 1 << endl; //~ cin >> h; ans[pos + 1] = n - h; vis[n - h] = 1; v[pos] = h; } bool flag = true; for(l = pos - 2; l>=1; l--){ h = query(l, l+1); //~ cout << l << " " << l + 1 << endl; //~ cin >> h; v[l] = h; if(vis[ans[l+1]+h] == 1 || ans[l+1] + h > n){ ans[l] = ans[l+1] - h; vis[ans[l+1] - h] = 1; flag = true; continue; } if(vis[ans[l+1]-h] == 1 || ans[l+1] - h < 1){ ans[l] = ans[l+1] + h; vis[ans[l+1] + h] = 1; flag = false; continue; } if(flag){ u = query(l, l + 2); //~ cout << l << " " << l + 2 << endl; //~ cin >> u; if(v[l+1] + h != u){ ans[l] = ans[l+1] + h; vis[ans[l+1] + h] = 1; flag = false; } else{ ans[l] = ans[l+1] - h; vis[ans[l+1] - h] = 1; flag = true; } } else if(!flag){ u = query(l, l + 2); //~ cout << l << " " << l + 2 << endl; //~ cin >> u; if(v[l+1] + u == h){ ans[l] = ans[l+1] - h; vis[ans[l+1] - h] = 1; flag = true; } else{ ans[l] = ans[l+1] + h; vis[ans[l+1] + h] = 1; flag = false; } } } //------------------------------------------------------------------------- flag = true; for(l = pos + 2; l <= n; l++){ h = query(l-1, l); //~ cout << l - 1 << " " << l << endl; //~ cin >> h; v[l-1] = h; if(vis[ans[l-1]+h] == 1 || ans[l-1] + h > n){ ans[l] = ans[l-1] - h; vis[ans[l-1] - h] = 1; flag = true; continue; } if(vis[ans[l-1]-h] == 1 || ans[l-1] - h < 1){ ans[l] = ans[l-1] + h; vis[ans[l-1] + h] = 1; flag = false; continue; } if(flag){ u = query(l-2, l); //~ cout << l - 2<< " " << l << endl; //~ cin >> u; if(v[l-2] + h != u){ ans[l] = ans[l-1] + h; vis[ans[l-1] + h] = 1; flag = false; } else{ ans[l] = ans[l-1] - h; vis[ans[l-1] - h] = 1; flag = true; } } else if(!flag){ u = query(l-2, l); //~ cout << l - 2 << " " << l << endl; //~ cin >> u; if(v[l-2] + u == h){ ans[l] = ans[l-1] - h; vis[ans[l-1] - h] = 1; flag = true; } else{ ans[l] = ans[l-1] + h; vis[ans[l-1] + h] = 1; flag = false; } } } for(int i = 1;i<=n;i++)answer(i, ans[i]); return; } /* */ //~ signed main() //~ { // freopen("seq.in", "r", stdin); // freopen("seq.out", "w", stdout); //~ ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL); //~ int tt=1;//cin>>tt; //~ while(tt--)solve(5); //~ }

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

xylophone.cpp:27:22: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+17' to '2147483647' [-Woverflow]
   27 | const int inf = 1e17 + 7;
      |                 ~~~~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...