結果
問題 | No.808 Kaiten Sushi? |
ユーザー | yyyuuuummmmaaa1 |
提出日時 | 2019-07-24 03:27:20 |
言語 | C++11 (gcc 11.4.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,384 bytes |
コンパイル時間 | 2,111 ms |
コンパイル使用メモリ | 171,048 KB |
実行使用メモリ | 22,180 KB |
最終ジャッジ日時 | 2023-09-09 09:11:56 |
合計ジャッジ時間 | 11,810 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,380 KB |
testcase_01 | AC | 1 ms
4,376 KB |
testcase_02 | AC | 2 ms
4,376 KB |
testcase_03 | AC | 2 ms
4,384 KB |
testcase_04 | AC | 1 ms
4,376 KB |
testcase_05 | AC | 1 ms
4,376 KB |
testcase_06 | AC | 1 ms
4,376 KB |
testcase_07 | AC | 3 ms
4,376 KB |
testcase_08 | AC | 4 ms
4,376 KB |
testcase_09 | AC | 5 ms
4,380 KB |
testcase_10 | AC | 4 ms
4,380 KB |
testcase_11 | AC | 3 ms
4,380 KB |
testcase_12 | WA | - |
testcase_13 | AC | 4 ms
4,380 KB |
testcase_14 | WA | - |
testcase_15 | WA | - |
testcase_16 | AC | 4 ms
4,380 KB |
testcase_17 | AC | 3 ms
4,376 KB |
testcase_18 | AC | 2 ms
4,376 KB |
testcase_19 | AC | 2 ms
4,380 KB |
testcase_20 | AC | 2 ms
4,380 KB |
testcase_21 | AC | 2 ms
4,384 KB |
testcase_22 | AC | 2 ms
4,384 KB |
testcase_23 | AC | 68 ms
10,744 KB |
testcase_24 | AC | 55 ms
9,224 KB |
testcase_25 | AC | 58 ms
10,184 KB |
testcase_26 | AC | 55 ms
9,740 KB |
testcase_27 | AC | 196 ms
18,864 KB |
testcase_28 | AC | 53 ms
8,388 KB |
testcase_29 | AC | 184 ms
18,156 KB |
testcase_30 | AC | 113 ms
12,960 KB |
testcase_31 | AC | 207 ms
19,696 KB |
testcase_32 | AC | 238 ms
21,888 KB |
testcase_33 | AC | 110 ms
12,884 KB |
testcase_34 | WA | - |
testcase_35 | AC | 164 ms
16,620 KB |
testcase_36 | WA | - |
testcase_37 | AC | 2 ms
4,380 KB |
testcase_38 | AC | 1 ms
4,380 KB |
testcase_39 | WA | - |
testcase_40 | AC | 53 ms
7,556 KB |
testcase_41 | AC | 53 ms
8,188 KB |
testcase_42 | AC | 212 ms
17,492 KB |
testcase_43 | WA | - |
testcase_44 | AC | 152 ms
14,460 KB |
testcase_45 | AC | 74 ms
9,564 KB |
testcase_46 | WA | - |
testcase_47 | AC | 289 ms
22,160 KB |
testcase_48 | WA | - |
testcase_49 | WA | - |
testcase_50 | AC | 296 ms
22,116 KB |
testcase_51 | AC | 290 ms
22,180 KB |
testcase_52 | AC | 141 ms
16,948 KB |
testcase_53 | AC | 196 ms
21,792 KB |
testcase_54 | AC | 1 ms
4,380 KB |
testcase_55 | AC | 2 ms
4,376 KB |
testcase_56 | AC | 2 ms
4,380 KB |
testcase_57 | AC | 64 ms
9,884 KB |
testcase_58 | AC | 105 ms
13,340 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; typedef long long ll; vector<int>solve2(const vector<int>&v,int from){ vector<int>que; map<int,int>mp; for(int x=from;x<v.size();++x){ if(mp.find(v[x])==mp.end()){ que.emplace_back(v[x]); mp[v[x]]=que.size()-1; }else{ while(true){ int aback=que.back(); mp.erase(aback); que.pop_back(); if(aback==v[x])break; } } } return que; } vector<int> solve(int N,long long int K,vector<int>v,int start){ vector<int>rs(N); { map<int,int>mp; for(int i=N-1;i>=0;--i){ mp[v[i]]=N+i; } for(int i=N-1;i>=0;--i){ rs[i]=mp[v[i]]; mp[v[i]]=i; } } long long int ny=0,nx=start; map<int,long long int>mp; mp[start]=0; while(true){ //cout<<nx<<ny<<endl; auto next_x=rs[nx]; long long next_y=ny; //cout<<next_x<<' '<<next_y<<endl; if(next_x>=N){ next_y++; next_x-=N; } next_x++; if(next_x>=N){ next_y++; next_x-=N; } if(next_y>=K){ if(K-1==next_y){ v.insert(v.end(),v.begin(),v.end()); } return solve2(v,nx); }else{ ny=next_y; nx=next_x; if(mp.find(nx)==mp.end()){ mp[nx]=ny; }else{ long long sa=-(mp[nx]-ny); long long int rest=K-ny; rest%=sa; //cout<<rest<<endl; if(rest==0)rest=sa; long long xx=K%sa; if(xx==0)xx=sa; assert(nx==0); return solve(N,xx,v,0); } } } assert(false); } #define WHATS(var) cout<<#var<<"="<<var<<endl; int main() { ios::sync_with_stdio(false); int N,M;cin>>N>>M; set<int>sushis,teas; for(int i=0;i<N;++i){ int a;cin>>a; sushis.emplace(a); sushis.emplace(a+M); } for(int i=0;i<N;++i){ int a;cin>>a; teas.emplace(a); teas.emplace(a+M); } long long int answer=0; int now=0; for(int i=0;i<N;++i){ auto it=sushis.lower_bound(now); answer+=*it-now; now=*it; sushis.erase(now); int nn=now>=M?now-M:now+M; sushis.erase(nn); if(nn<now)swap(now,nn); //cout<<now<<endl; auto jt=teas.lower_bound(now); auto lt=jt; if(!sushis.empty()){ auto kt=sushis.lower_bound(*jt); //WHATS(*kt); //WHATS(*teas.upper_bound(*kt)); //WHATS(*prev(teas.upper_bound(*kt))); lt=prev(teas.upper_bound(*kt)); } answer+=*lt-now; now=*lt; nn =now>=M?now-M:now+M; //cout<<now<<endl; teas.erase(nn); teas.erase(now); if(nn<now)swap(now,nn); //cout<<now<<endl; } cout<<answer<<endl; return 0; }