2018-2019|2018-2019, ICPC, Asia Yokohama Regional Contest 2018 K AsiaYokohamaRegionalContest2018K|ICP

2018-2019, ICPC, Asia Yokohama Regional Contest 2018 K传送门：https://codeforces.com/gym/102082/attachments
题解:
【2018-2019|2018-2019, ICPC, Asia Yokohama Regional Contest 2018 K】代码：

文章图片

文章图片

/** *┏┓┏┓ *┏┛┗━━━━━━━┛┗━━━┓ *┃┃ *┃━┃ *┃　＞＜　┃ *┃┃ *┃...　⌒　...┃ *┃┃ *┗━┓┏━┛ *┃┃　Code is far away from bug with the animal protecting *┃┃神兽保佑,代码无bug *┃┃ *┃┃ *┃┃ *┃┃ *┃┗━━━┓ *┃┣┓ *┃┏┛ *┗┓┓┏━┳┓┏┛ *┃┫┫　┃┫┫ *┗┻┛　┗┻┛ */ #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long LL; typedef pair pLL; typedef pair pLi; typedef pair pil; ; typedef pair pii; typedef unsigned long long uLL; #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 #define bug printf("*********\n") #define FIN freopen("input.txt","r",stdin); #define FON freopen("output.txt","w+",stdout); #define IO ios::sync_with_stdio(false),cin.tie(0) #define debug1(x) cout<<"["<<#x<<" "<<(x)<<"]\n" #define debug2(x,y) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<"]\n" #define debug3(x,y,z) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<" "<<#z<<" "< '9') { if(ch == '-')f = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } return x * f; } const double eps = 1e-8; const int mod = 1e9 + 7; const int maxn = 3e5 + 5; const int INF = 0x3f3f3f3f; const LL INFLL = 0x3f3f3f3f3f3f3f3f; int n; int num; vector aa; vector a; vector b; int get_ans() { vector tmpa; tmpa = a; vector tmpb; tmpb = b; sort(tmpa.begin(), tmpa.end()); sort(tmpb.begin(), tmpb.end()); int ans = 0; int tmp = 0; for(int i = 0; i < n; i++) { if(tmp == n) break; if(tmpa[tmp] < tmpb[i]) { ans++; tmp++; } } return ans; } int len; bool check(int pos, int mid) { int res = 0; int tmp = 0; for(int i = 0; i < len; i++) { if(i == mid) continue; if(tmp == n) continue; while(tmp < n && aa[tmp].second <= pos) tmp++; if(aa[tmp].first < b[i]) tmp++, res++; } if(res == num) return 1; else { if(res + (b[mid] > a[pos]) == num) return 1; else if(res + (b[len - 1] > a[pos]) == num) return 1; else return 0; } } int main() { #ifndef ONLINE_JUDGE FIN #endif scanf("%d", &n); for(int i = 0, x; i < n; i++) { scanf("%d", &x); a.push_back(x); aa.push_back(make_pair(x, i)); } for(int i = 1, x; i <= n; i++) { scanf("%d", &x); b.push_back(x); } sort(aa.begin(), aa.end()); sort(b.begin(), b.end()); num = get_ans(); vector ans; for(int i = 0; i < n; i++) { len = b.size() ; int l = 0, r = len - 1; while(r - l > 1) { int mid = (l + r) >> 1; // debug1(num); // debug3(l, r, mid); if(check(i, mid)) { l = mid; } else { r = mid; } } // debug1(l); // debug3(r, (int)check(i, r), num); if(check(i, r)) { ans.push_back(b[r]); num -= a[i] < b[r]; b.erase(b.begin() + r); } else { ans.push_back(b[l]); num -= a[i] < b[l]; b.erase(b.begin() + l); } } for(int i = 0; i < ans.size(); i++) { printf("%d%c", ans[i], i == ans.size() - 1 ? '\n' : ' '); } return 0; } close