IJPC-01
IJPC-01に参加した。
B:silver
問題文読んでqnighyさんだな〜と思う。
座標圧縮+何かかなぁ〜→全部一度に求められる→座標圧縮とかする必要ないなぁ、で満点。
簡単なのにuniqueの亜種っぽいことしてなくてAC状況が気持ち悪いことになってた。(大きいケースになるほどACが増える)
#include"grader.h" #include"silver.h" #include"grader.cpp" #include<stdio.h> #include<vector> #include<algorithm> #include<deque> using namespace std; typedef pair<int,int> pii; pii maxi[100001]; int beg[100001]; int flag[100000]; void schedule(int day,int tes,int tests[],int ei[]) { vector<pii>vec; for(int i=0;i<tes;i++) { vec.push_back(make_pair(max(tests[i]-ei[i]+1,0),-1)); vec.push_back(make_pair(min(tests[i]+ei[i]-1,day-1),1)); } sort(vec.begin(),vec.end()); deque<pii>deq; for(int p=0;p<vec.size();p++) { if(vec[p].second==1) { deq.push_back(vec[p]); } else { if(!deq.empty()) { if(deq[deq.size()-1]==make_pair(vec[p].first-1,1)) { deq.pop_back(); } else { deq.push_back(vec[p]); } } else { deq.push_back(vec[p]); } } } vec.clear(); for(int r=0;r<deq.size();r++) { vec.push_back(deq[r]); } int now=0; fill(maxi,maxi+100001,make_pair(-1,-1)); fill(beg,beg+100001,-1); for(int j=0;j<vec.size();j++) { if(vec[j].second==-1) { now++; beg[now]=vec[j].first; } else { if(maxi[now].first<vec[j].first-beg[now]) { maxi[now]=make_pair(vec[j].first-beg[now],beg[now]); } now--; } } for(int k=1;k<=tes;k++) { if(maxi[k]==make_pair(-1,-1)) { answer(k,0,0); } else { answer(k,maxi[k].second,maxi[k].second+maxi[k].first); } } }
A:問題名長い
とりあえず普通にO(n^2)を実装して20点取る。あとは適当にifで分岐させて直線の場合だけとる。45点。
n^2より直線思いつくのに時間かかった(謎)
iterationすぐREでてむずい。
#include"animals.h" #include"grader.cpp" #include<stdio.h> #include<algorithm> #include<vector> #include<set> using namespace std; typedef pair<int,int> pii; typedef pair<int,pii>pi3; int par[100000]; vector<int>pat[100000]; vector<int>ko[100000]; set<pii>se; void dfs(int a) { for(int i=0;i<pat[a].size();i++) { if(par[pat[a][i]]==-1) { par[pat[a][i]]=a; dfs(pat[a][i]); ko[a].push_back(pat[a][i]); } } } int ren(int a) { int sum=0; for(int i=0;i<ko[a].size();i++) { sum+=ren(ko[a][i]); } sum++; return sum; } int parent(int a) { for(;;) { if(par[a]==-2) { return a; } a=par[a]; } } int kaz; set<pii>mse; multiset<int>answ; void init(int num,int edge[][2]) { kaz=num; if(num<=1000) { for(int i=0;i<num;i++) { pat[edge[i][0]].push_back(edge[i][1]); pat[edge[i][1]].push_back(edge[i][0]); } fill(par,par+100000,-1); par[0]=-2; dfs(0); se.insert(make_pair(num,0));/* for(int i=0;i<num;i++) { printf("%d\n",par[i]); }*/ } else { mse.insert(make_pair(0,num-1)); answ.insert(num); } } int query(int des) { if(kaz<=1000) { int pa=parent(des); se.erase(make_pair(ren(pa),pa)); for(int i=0;i<ko[des].size();i++) { par[ko[des][i]]=-2; se.insert(make_pair(ren(ko[des][i]),ko[des][i])); } ko[des].clear(); if(par[des]!=-2) { int hoge=0; for(int p=0;p<ko[par[des]].size();p++) { if(hoge==1) { ko[par[des]][p-1]=ko[par[des]][p]; } if(ko[par[des]][p]==des) { hoge=1; } } ko[par[des]].pop_back(); par[des]=-2; } se.insert(make_pair(ren(pa),pa)); set<pii>::iterator it=se.end(); it--; pii ret=*it;/* for(int q=0;q<kaz;q++) { for(int r=0;r<ko[q].size();r++) { printf("%d ",ko[q][r]); } printf("\n"); }*/ return ret.first; } else { set<pii>::iterator ite; ite=mse.lower_bound(make_pair(des,10000000)); ite--; pii fuga=*ite; multiset<int>::iterator iter=answ.find(fuga.second-fuga.first+1); answ.erase(iter); answ.insert(des-fuga.first); answ.insert(fuga.second-des); mse.erase(ite); mse.insert(make_pair(fuga.first,des-1)); mse.insert(make_pair(des+1,fuga.second)); iter=answ.end(); iter--; int ret=*iter; return ret; } }
C:training
適当にやるだけ実装して12点。O(QNlog N)で30点来るらしい。N<=5000だし無理だと思ってた。実装すればよかった。
#include"training.h" #include"grader.cpp" #include<stdio.h> #include<algorithm> #include<vector> using namespace std; typedef pair<int,int> pii; vector<int>map; void init(int num,int data[]) { for(int i=0;i<num;i++) { map.push_back(data[i]); } } void update(int a,int b) { map[a]=b; } int train(int a,int b) { int sum=0; for(int i=a;i<=b;i++) { for(int j=i+1;j<=b;j++) { if(map[i]>map[j]) { sum++; } } } return sum; }