何だこのセットは......。難問が誰にも存在しないセットだと、簡単が速いから勝ててしまう。
| A | B | C | D | E | F | Place |
|---|---|---|---|---|---|---|
| 00:13 | 00:06 | 00:34 (+1) | 00:48 | - | - | 4th |
A:
逆からやるだけ。
#include<stdio.h> #include<math.h> #include<algorithm> #include<queue> #include<string> #include<string.h> #include<vector> #include<set> #include<map> #include<stdlib.h> using namespace std; const long long mod=1000000007; const long long inf=mod*mod; int p[11000][4]; int mat[110][110]; int main(){ int a,b,c;scanf("%d%d%d",&a,&b,&c); for(int i=0;i<c;i++){ scanf("%d%d",&p[i][0],&p[i][1]); p[i][1]--; if(p[i][0]==3){ scanf("%d%d",&p[i][2],&p[i][3]); p[i][2]--; } } for(int i=c-1;i>=0;i--){ if(p[i][0]==3){ mat[p[i][1]][p[i][2]]=p[i][3]; }else if(p[i][0]==2){ int tmp=mat[a-1][p[i][1]]; for(int j=a-1;j>0;j--){ mat[j][p[i][1]]=mat[j-1][p[i][1]]; } mat[0][p[i][1]]=tmp; }else{ int tmp=mat[p[i][1]][b-1]; for(int j=b-1;j>0;j--){ mat[p[i][1]][j]=mat[p[i][1]][j-1]; } mat[p[i][1]][0]=tmp; } } for(int i=0;i<a;i++){ for(int j=0;j<b;j++){ if(j)printf(" "); printf("%d",mat[i][j]); } printf("\n"); } }
B:
偶奇ごとに持っておけば、偶数奇数それぞれの中では平行移動してるだけ。
#include<stdio.h> #include<math.h> #include<algorithm> #include<queue> #include<string> #include<string.h> #include<vector> #include<set> #include<map> #include<stdlib.h> using namespace std; const long long mod=1000000007; const long long inf=mod*mod; int ret[1100000]; int main(){ int a,b;scanf("%d%d",&a,&b); int p1=0; int p2=1; while(b--){ int c;scanf("%d",&c); if(c==1){ int d;scanf("%d",&d); p1+=d; p2+=d; if(p1<0)p1+=a; if(p2<0)p2+=a; if(p1>=a)p1-=a; if(p2>=a)p2-=a; }else{ p1^=1; p2^=1; } } for(int i=0;i<a/2;i++){ ret[(p1+i*2)%a]=i*2+1; ret[(p2+i*2)%a]=i*2+2; } for(int i=0;i<a;i++){ if(i)printf(" "); printf("%d",ret[i]); } printf("\n"); }
C:
手元で二次方程式を解く・sqrtの中身を負にしないように
#include<stdio.h> #include<math.h> #include<algorithm> #include<queue> #include<string> #include<string.h> #include<vector> #include<set> #include<map> #include<stdlib.h> using namespace std; const long long mod=1000000007; const long long inf=mod*mod; double A[110000]; double B[110000]; double x[110000]; double y[110000]; int main(){ int a;scanf("%d",&a); for(int i=0;i<a;i++)scanf("%lf",A+i); for(int i=0;i<a;i++)scanf("%lf",B+i); double p1=0; double p2=0; for(int i=0;i<a;i++)p2+=B[i]; for(int i=0;i<a-1;i++){ p1+=A[i]; p2-=B[i]; y[i]=0.5*((p1-p2+1)+sqrt(max(0.0,(p1-p2+1)*(p1-p2+1)-4.0*p1))); x[i]=0.5*((p1-p2+1)-sqrt(max(0.0,(p1-p2+1)*(p1-p2+1)-4.0*p1))); } x[a-1]=y[a-1]=1; for(int i=a-1;i>0;i--){ x[i]-=x[i-1]; y[i]-=y[i-1]; } for(int i=0;i<a;i++){ if(i)printf(" "); printf("%.12f",x[i]); } printf("\n"); for(int i=0;i<a;i++){ if(i)printf(" "); printf("%.12f",y[i]); } printf("\n"); }
D:
追加する数ごとに独立で、内部でも座標圧縮してBITするだけ...。残り2問と比べてあまりにも簡単すぎる。
#include<stdio.h> #include<math.h> #include<algorithm> #include<queue> #include<string> #include<string.h> #include<vector> #include<set> #include<map> #include<stdlib.h> using namespace std; const long long mod=1000000007; const long long inf=mod*mod; int x[110000]; int b[110000]; int t[110000]; int z[110000]; vector<int>q[110000]; int bit[110000]; int sz; int sum(int a,int b){ if(a)return sum(0,b)-sum(0,a-1); int ret=0; for(;b>=0;b=(b&(b+1))-1)ret+=bit[b]; return ret; } void add(int a,int b){ for(;a<sz;a|=a+1)bit[a]+=b; } int z2[110000]; int ans[110000]; int main(){ int a;scanf("%d",&a); for(int i=0;i<a;i++){ scanf("%d%d%d",b+i,t+i,x+i); z[i]=x[i]; } std::sort(z,z+a); for(int i=0;i<a;i++){ int at=lower_bound(z,z+a,x[i])-z; q[at].push_back(i); } for(int i=0;i<a;i++){ if(q[i].size()){ sz=q[i].size(); for(int j=0;j<q[i].size();j++){ z2[j]=t[q[i][j]]; } std::sort(z2,z2+sz); for(int j=0;j<q[i].size();j++){ int ind=lower_bound(z2,z2+sz,t[q[i][j]])-z2; if(b[q[i][j]]==1){ add(ind,1); }else if(b[q[i][j]]==2){ add(ind,-1); }else{ ans[q[i][j]]=sum(0,ind); } } for(int j=0;j<sz;j++)bit[j]=0; } } for(int i=0;i<a;i++){ if(b[i]!=3)continue; printf("%d\n",ans[i]); } }
F:
虚無。
Black box linear algebraを勉強する(これも虚無)か、虚無を実装するか。木分解でもうまくいきそうに見えるけどどうなんだこれ。
