JOI合宿問題

合宿問題でジャッジでACをとった問題でUPするだけの価値のあるもののソースを張っていきます。

Fish(この間のせた)

#include<stdio.h>
#include<vector>
#include<algorithm>
#include<set>
using namespace std;
typedef long long ll;
typedef pair<ll,ll>pii;
typedef pair<ll,pii>pi3;
int main()
{
    int num;
        scanf("%d",&num);
        vector<int>va,vb,vc;
        for(int i=0;i<num;i++)
        {
                int za;
                char zb;
                scanf("%d %c",&za,&zb);
                if(zb=='R')
                {
                        va.push_back(za);
                }
                if(zb=='G')
                {
                        vb.push_back(za);
                }
                if(zb=='B')
                {
                        vc.push_back(za);
                }
        }
        sort(va.begin(),va.end());
        sort(vb.begin(),vb.end());
        sort(vc.begin(),vc.end());
        vector<pi3>vec;
        for(int i=0;i<va.size();i++)
        {
                int lowa=lower_bound(va.begin(),va.end(),va[i])-va.begin();
                int uppa=upper_bound(va.begin(),va.end(),va[i]*2-1)-va.begin();
                int lowb=lower_bound(vb.begin(),vb.end(),va[i])-vb.begin();
                int uppb=upper_bound(vb.begin(),vb.end(),va[i]*2-1)-vb.begin();
                int lowc=lower_bound(vc.begin(),vc.end(),va[i])-vc.begin();
                int uppc=upper_bound(vc.begin(),vc.end(),va[i]*2-1)-vc.begin();
                vec.push_back(make_pair(uppa-lowa+1,make_pair(uppb-lowb+1,uppc-lowc+1)));
        }
        for(int i=0;i<vb.size();i++)
        {
                int lowa=lower_bound(va.begin(),va.end(),vb[i])-va.begin();
                int uppa=upper_bound(va.begin(),va.end(),vb[i]*2-1)-va.begin();
                int lowb=lower_bound(vb.begin(),vb.end(),vb[i])-vb.begin();
                int uppb=upper_bound(vb.begin(),vb.end(),vb[i]*2-1)-vb.begin();
                int lowc=lower_bound(vc.begin(),vc.end(),vb[i])-vc.begin();
                int uppc=upper_bound(vc.begin(),vc.end(),vb[i]*2-1)-vc.begin();
                vec.push_back(make_pair(uppa-lowa+1,make_pair(uppb-lowb+1,uppc-lowc+1)));
        }
        for(int i=0;i<vc.size();i++)
        {
                int lowa=lower_bound(va.begin(),va.end(),vc[i])-va.begin();
                int uppa=upper_bound(va.begin(),va.end(),vc[i]*2-1)-va.begin();
                int lowb=lower_bound(vb.begin(),vb.end(),vc[i])-vb.begin();
                int uppb=upper_bound(vb.begin(),vb.end(),vc[i]*2-1)-vb.begin();
                int lowc=lower_bound(vc.begin(),vc.end(),vc[i])-vc.begin();
                int uppc=upper_bound(vc.begin(),vc.end(),vc[i]*2-1)-vc.begin();
                vec.push_back(make_pair(uppa-lowa+1,make_pair(uppb-lowb+1,uppc-lowc+1)));
        }
        sort(vec.begin(),vec.end());
        reverse(vec.begin(),vec.end());
        set<pii>se;
        se.insert(make_pair(0,2000000000));
        se.insert(make_pair(2000000000,0));
        ll ans=0;
        ll men=0;
        for(int i=0;i<num;i++)
        {
                set<pii>::iterator it=se.lower_bound(vec[i].second);
                pii zan=*it;
                if(vec[i].second.first>zan.first||vec[i].second.second>zan.second)
                {
                        for(;;)
                        {
                                it--;
                                zan=*it;
                                if(vec[i].second.first>=zan.first&&vec[i].second.second>=zan.second)
                                {
                                        it--;
                                        pii zan2=*it;
                                        it++;
                                        it++;
                                        pii zan3=*it;
                                        it--;
                                        men-=(zan.first-zan2.first)*(zan.second-zan3.second);
                                        se.erase(it++);
                                }
                                else
                                {
                                        break;
                                }
                        }
                        it=se.lower_bound(vec[i].second);
                        pii zan3=*it;
                        it--;
                        pii zan2=*it;
                        men+=(vec[i].second.first-zan2.first)*(vec[i].second.second-zan3.second);
                        se.insert(vec[i].second);
                }
                if(i==num-1)
                {
                        ans+=men*vec[i].first;
                }
                else
                {
                        ans+=men*(vec[i].first-vec[i+1].first);
                }
        }
        printf("%lld\n",ans-1);
}

JOI flag(実装だいぶ適当)

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
#define mp(A,B) make_pair(A,B)
#define mt(A,B,C) mp(mp(A,B),C)
#define mq(A,B,C,D) mp(mp(A,B),mp(C,D))
typedef pair<int,int>pii;
typedef pair<pii,int>pi3;
typedef pair<pii,pii>pi4;
pi4 calc(vector<pi3>vec,int lx,int ly,int hen)
{
	if(vec.empty())
	{
		return mq(0,0,0,0);
	}
	if(hen==1)
	{
		if(vec[0].second==0)
		{
			return mq(0,1,1,0);
		}
		if(vec[0].second==1)
		{
			return mq(1,0,1,0);
		}
		if(vec[0].second==2)
		{
			return mq(1,1,0,0);
		}
	}
	vector<pi3>v11,v12,v21,v22;
	int n1=0,n2=0,n3=0;
	for(int i=0;i<vec.size();i++)
	{
		if(vec[i].first.first<lx+hen/2)
		{
			if(vec[i].first.second<ly+hen/2)
			{
				v11.push_back(vec[i]);
			}
			else
			{
				v12.push_back(vec[i]);
			}
		}
		else
		{
			if(vec[i].first.second<ly+hen/2)
			{
				v21.push_back(vec[i]);
			}
			else
			{
				v22.push_back(vec[i]);
			}
		}
		if(vec[i].second==0)
		{
			n2++;
			n3++;
		}
		if(vec[i].second==1)
		{
			n1++;
			n3++;
		}
		if(vec[i].second==2)
		{
			n1++;
			n2++;
		}
	}
	vector<pi4>r;
	r.resize(4);
	r[0]=calc(v11,lx,ly,hen/2);
	r[1]=calc(v12,lx,ly+hen/2,hen/2);
	r[2]=calc(v21,lx+hen/2,ly,hen/2);
	r[3]=calc(v22,lx+hen/2,ly+hen/2,hen/2);
	vector<int>per;
	for(int i=0;i<4;i++)
	{
		per.push_back(i);
	}
	int mini=1<<30;
	for(;;)
	{
		mini=min(mini,r[per[0]].first.first+r[per[1]].first.second+r[per[2]].second.first+r[per[3]].second.second);
		if(!next_permutation(per.begin(),per.end()))
		{
			break;
		}
	}
	return mq(n1,n2,n3,mini);
}
int main()
{
	int num,hen;
	scanf("%d%d",&hen,&num);
	vector<pi3>vec;
	for(int i=0;i<num;i++)
	{
		int za,zb;
		char zc;
		scanf("%d%d %c",&za,&zb,&zc);
		za--;
		zb--;
		if(zc=='J')
		{
			vec.push_back(mt(za,zb,0));
		}
		if(zc=='O')
		{
			vec.push_back(mt(za,zb,1));
		}
		if(zc=='I')
		{
			vec.push_back(mt(za,zb,2));
		}
	}
	printf("%d\n",calc(vec,0,0,1<<hen).second.second);
}

Lines 有理数でやってるので誤差とは無縁 そのかわり0除算が怖いので分岐が多くなってる

#include<stdio.h>
#include<vector>
#include<algorithm>
#include<stdlib.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll>pii;
typedef pair<pii,ll>pi3;
typedef pair<pii,pii>pi4;
ll gcd(ll a,ll b)
{
  if(a==0)
    {
      return b;
    }
  if(b==0)
    {
      return a;
    }
  for(;;)
    {
      if(a<b)
	{
	  swap(a,b);
	}
      a%=b;
      if(a==0)
	{
	  return b;
	}
    }
}
pi3 toline(ll a,ll b,ll c,ll d)
{
  if(d<b)
    {
      swap(a,c);
      swap(b,d);
    }
  if(d==b)
    {
      return make_pair(make_pair(0,1),d);
    }
  if(a==c)
    {
      return make_pair(make_pair(1,0),a);
    }
  if(a*d==b*c)
    {
      ll g=gcd(abs(d-b),abs(a-c));
      return make_pair(make_pair((d-b)/g,(a-c)/g),0);
    }
  ll g=gcd(gcd(abs(d-b),abs(a-c)),abs(a*d-b*c));
  return make_pair(make_pair((d-b)/g,(a-c)/g),(a*d-b*c)/g);
}
pi4 cross(pi3 a,pi3 b)
{
  pii x=make_pair((a.second*b.first.second-b.second*a.first.second),(a.first.first*b.first.second-a.first.second*b.first.first));
  if(x.second<0)
    {
      x.first=-x.first;
      x.second=-x.second;
    }
  ll g=gcd(abs(x.first),abs(x.second));
  x.first/=g;
  x.second/=g;
  swap(a.first.second,a.first.first);
  swap(b.first.second,b.first.first);
  pii y=make_pair((a.second*b.first.second-b.second*a.first.second),(a.first.first*b.first.second-a.first.second*b.first.first));
  if(y.second<0)
    {
      y.first=-y.first;
      y.second=-y.second;
    }
  g=gcd(abs(y.first),abs(y.second));
  y.first/=g;
  y.second/=g;
  return make_pair(x,y);
}
int count(vector<pi4>a)
{
  sort(a.begin(),a.end());
  pi4 now=make_pair(make_pair(523453423434LL,5876567587LL),make_pair(78957826239LL,356238963LL));
  int ret=0;
  for(int i=0;i<a.size();i++)
    {
      if(now!=a[i])
	{
	  now=a[i];
	  ret++;
	}
    }
  return ret;
}
int main()
{
  int num;
  scanf("%d",&num);
  vector<pi3>vec;
  for(int i=0;i<num;i++)
    {
      ll za,zb,zc,zd;
      scanf("%lld%lld%lld%lld",&za,&zb,&zc,&zd);
      vec.push_back(toline(za,zb,zc,zd));
      pi3 zan=toline(za,zb,zc,zd);
    }
  pi3 now=make_pair(make_pair(0,0),0);
  vector<pi3>zv;
  sort(vec.begin(),vec.end());
  for(int i=0;i<num;i++)
    {
      if(now!=vec[i])
	{
	  now=vec[i];
	  zv.push_back(now);
	  //printf("%lld x+%lld y=%lld\n",now.first.first,now.first.second,now.second);
	}
    }
  vec=zv;
  vector<pi4>point;
  int ans=1;
  for(int i=0;i<vec.size();i++)
    {
      vector<pi4>zp;
      for(int j=0;j<vec.size();j++)
	{
	  //printf("%d %d\n",i,j);
	  if(i==j)
	    {
	      continue;
	    }
	  if(vec[i].first.first*vec[j].first.second!=vec[i].first.second*vec[j].first.first)
	    {
	      pi4 z=cross(vec[i],vec[j]);
	      //printf("(%lld / %lld) (%lld / %lld)\n",z.first.first,z.first.second,z.second.first,z.second.second);
	      zp.push_back(z);
	      point.push_back(z);
	    }
	}
      ans+=count(zp)+1;
    }
  ans-=count(point);
  printf("%d\n",ans);
}

Flu setでごりごりしたらTLEしたのでおとなしくバケット組んだ(そっちのほうが実装軽い)

#include<stdio.h>
#include<vector>
#include<algorithm>
#include<set>
#include<queue>
using namespace std;
typedef pair<int,int>pii;
typedef pair<pii,int>pi3;
vector<int>pat[100000];
int flag[100000];
vector<pi3>brk[42][42];
int main()
{
	int cit,nic,dis,gen;
	scanf("%d%d%d%d",&cit,&nic,&dis,&gen);
	vector<pi3>vec;
	for(int i=0;i<cit;i++)
	{
		int za,zb;
		scanf("%d%d",&za,&zb);
		vec.push_back(make_pair(make_pair(za,zb),i));
		brk[za/25+1][zb/25+1].push_back(make_pair(make_pair(za,zb),i));
	}
	int pt=0;
	for(int i=0;i<cit;i++)
	{
		for(int j=-1;j<=1;j++)
		{
			for(int k=-1;k<=1;k++)
			{
				vector<pi3>v=brk[vec[i].first.first/25+1+j][vec[i].first.second/25+1+k];
				for(int p=0;p<v.size();p++)
				{
					pii zan=v[p].first;
					if((zan.first-vec[i].first.first)*(zan.first-vec[i].first.first)+(zan.second-vec[i].first.second)*(zan.second-vec[i].first.second)<=dis*dis)
					{
						pat[i].push_back(v[p].second);
						pat[v[p].second].push_back(i);
					}
				}
			}
		}
	}
	fill(flag,flag+cit,-1);
	queue<pii>que;
	que.push(make_pair(0,0));
	for(;;)
	{
		if(que.empty())
		{
			break;
		}
		pii zan=que.front();
		que.pop();
		if(flag[zan.first]!=-1)
		{
			continue;
		}
		flag[zan.first]=zan.second;
		for(int i=0;i<pat[zan.first].size();i++)
		{
			if(flag[pat[zan.first][i]]==-1)
			{
				que.push(make_pair(pat[zan.first][i],zan.second+1));
			}
		}
	}
	int ret=0;
	for(int i=0;i<cit;i++)
	{
		if(max(0,gen-nic+1)<=flag[i]&&flag[i]<=gen)
		{
			ret++;
		}
	}
	printf("%d\n",ret);
}

Typhoon BITやるだけ

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
int bit[262145];
void add(int a,int b)
{
	for(;;)
	{
		if(a>=262144)
		{
			break;
		}
		bit[a]+=b;
		a+=a&-a;
	}
}
int sum(int a)
{
	int ret=0;
	for(;;)
	{
		if(a==0)
		{
			break;
		}
		ret+=bit[a];
		a-=a&-a;
	}
	return ret;
}
#define mp(A,B) make_pair(A,B)
#define mq(A,B,C,D) mp(mp(A,B),mp(C,D))
typedef pair<int,int>pii;
typedef pair<pii,pii>pi4;
int ans[100000];
int main()
{
	int num,query,chi;
	scanf("%d%d%d",&num,&query,&chi);
	vector<pi4>vec;
	vector<int>uni;
	for(int i=0;i<num;i++)
	{
		int za,zb;
		scanf("%d%d",&za,&zb);
		uni.push_back(za-1);
		uni.push_back(zb);
		vec.push_back(mq(i+1,0,za,zb));
	}
	for(int j=0;j<num;j++)
	{
		int za,zb,zc;
		scanf("%d%d%d",&za,&zb,&zc);
		vec.push_back(mq(zb-1,1,za,j*2));
		vec.push_back(mq(zc,1,za,j*2+1));
	}
	sort(vec.begin(),vec.end());
	sort(uni.begin(),uni.end());
	vector<int>zuni;
	int now=-100000000;
	for(int i=0;i<uni.size();i++)
	{
		if(now!=uni[i])
		{
			zuni.push_back(uni[i]);
			now=uni[i];
		}
	}
	uni=zuni;/*
	for(int i=0;i<uni.size();i++)
	{
		printf("%d ",uni[i]);
	}
	printf("\n");*/
	for(int i=0;i<vec.size();i++)
	{/*
		for(int p=0;p<uni.size()+1;p++)
		{
			printf("%d ",sum(p+1));
		}
		printf("\n");
		printf("%d %d %d %d\n",vec[i].first.first,vec[i].first.second,vec[i].second.first,vec[i].second.second);*/
		if(vec[i].first.second==0)
		{
			int low1=lower_bound(uni.begin(),uni.end(),vec[i].second.first-1)-uni.begin();
			int low2=lower_bound(uni.begin(),uni.end(),vec[i].second.second)-uni.begin();
			add(low1+2,1);
			add(low2+2,-1);
		}
		else
		{
			int low=lower_bound(uni.begin(),uni.end(),vec[i].second.first)-uni.begin();
			if(vec[i].second.second%2==0)
			{
				ans[vec[i].second.second/2]-=sum(low+1);
			}
			else
			{
				ans[vec[i].second.second/2]+=sum(low+1);
			}
		}
	}
	for(int i=0;i<query;i++)
	{
		printf("%d\n",ans[i]);
	}
}

Ruins 簡単なDPだけど点が線の上にあるかの判定がきれいにいかない

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
typedef pair<int,int>pii;
bool han(pii a,pii b,pii c)
{
	if(b.first<a.first)
	{
		swap(a,b);
	}
	if(c.second*(b.first-a.first)>(b.second-a.second)*c.first-a.first*b.second+a.second*b.first)
	{
		return true;
	}
	else
	{
		return false;
	}
}
int dp[2][128][128][128];
int maxis[2][128][128];
int main()
{
	int num;
	scanf("%d",&num);
	vector<pii>vec;
	for(int i=0;i<num;i++)
	{
		int za,zb;
		scanf("%d%d",&za,&zb);
		vec.push_back(make_pair(za,zb));
	}
	sort(vec.begin(),vec.end());/*
	for(int i=0;i<num;i++)
	{
		printf(" %d %d\n",vec[i].first,vec[i].second);
	}*/
	for(int i=0;i<num;i++)
	{
		for(int j=i+1;j<num;j++)
		{
			dp[0][i][i][j]=1;
			dp[1][i][i][j]=1;
		}
	}/*
	for(int i=0;i<num;i++)
	{
		for(int j=i+1;j<num;j++)
		{
			for(int k=j+1;k<num;k++)
			{
				printf("%d %d %d  %d\n",i,j,k,int(han(vec[i],vec[j],vec[k])));
			}
		}
	}*/
	for(int i=0;i<num;i++)
	{
		for(int j=i;j<num;j++)
		{
			for(int k=j+1;k<num;k++)
			{
				for(int l=k+1;l<num;l++)
				{
					if(han(vec[j],vec[k],vec[l])&&dp[0][i][j][k]!=0)
					{
						dp[0][i][k][l]=max(dp[0][i][k][l],dp[0][i][j][k]+1);
					}
					if((!han(vec[j],vec[k],vec[l]))&&dp[1][i][j][k]!=0)
					{
						dp[1][i][k][l]=max(dp[1][i][k][l],dp[1][i][j][k]+1);
					}
				}
			}
		}
	}/*
	for(int i=0;i<num;i++)
	{
		for(int j=i+1;j<num;j++)
		{
			printf("debug:%d %d  %d %d\n",i,j,dp[0][0][i][j],dp[1][0][i][j]);
		}
	}*/
	int maxi=0;
	for(int i=0;i<num;i++)
	{
		for(int j=i;j<num;j++)
		{
			for(int k=i;k<j;k++)
			{
				maxis[0][i][j]=max(maxis[0][i][j],dp[0][i][k][j]);
				maxis[1][i][j]=max(maxis[1][i][j],dp[1][i][k][j]);
			}
			maxi=max(maxi,maxis[0][i][j]+maxis[1][i][j]);
			//printf("%d %d %d %d\n",i,j,maxis[0][i][j],maxis[1][i][j]);
		}
	}
	printf("%d\n",maxi);
}

Regions 簡単

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
typedef pair<int,int>pii;
vector<pii>pat[30000];
vector<pii>ko[30000];
bool flag[30000];
void dfs(int node)
{
	if(flag[node])
	{
		return;
	}
	flag[node]=true;
	for(int i=0;i<pat[node].size();i++)
	{
		if(!flag[pat[node][i].first])
		{
			ko[node].push_back(pat[node][i]);
			dfs(pat[node][i].first);
		}
	}
}
int ret;
int calc(int node,int med)
{
	vector<int>vec;
	for(int i=0;i<ko[node].size();i++)
	{
		vec.push_back(calc(ko[node][i].first,med)+ko[node][i].second);
	}
	sort(vec.begin(),vec.end());
	if(vec.empty())
	{
		return 0;
	}
	if(vec.size()==1)
	{
		if(vec[0]<=med)
		{
			return vec[0];
		}
		else
		{
			ret++;
			return 0;
		}
	}
	if(vec[vec.size()-2]+vec[vec.size()-1]<=med)
	{
		return vec[vec.size()-1];
	}
	else
	{
		for(int i=0;i<vec.size()-1;i++)
		{
			if(vec[i]+vec[i+1]>med)
			{
				ret+=vec.size()-i-1;
				return vec[i];
			}
		}
	}
}
int main()
{
	int cit,gen;
	scanf("%d%d",&cit,&gen);
	for(int i=0;i<cit-1;i++)
	{
		int za,zb,zc;
		scanf("%d%d%d",&za,&zb,&zc);
		za--;
		zb--;
		pat[za].push_back(make_pair(zb,zc));
		pat[zb].push_back(make_pair(za,zc));
	}
	fill(flag,flag+cit,false);
	dfs(0);
	int beg=0,end=3000000;
	for(;;)
	{
		int med=(beg+end)/2;
		ret=0;
		calc(0,med);
		ret++;
		if(ret>gen)
		{
			beg=med+1;
		}
		else
		{
			end=med;
		}
		if(beg==end)
		{
			printf("%d\n",beg);
			return 0;
		}
	}
}

DNA synthesizer ローリングハッシュ(想定解はTrieらしいがlogつけても間に合う)

#include<stdio.h>
#include<vector>
#include<algorithm>
#include<set>
#include<string>
#include<iostream>
using namespace std;
typedef long long ll;
ll mot=1000000007;
vector<ll>vec[21];
int poi[150000];
bool han(ll hash,int lon)
{
	return lower_bound(vec[lon].begin(),vec[lon].end(),hash)!=upper_bound(vec[lon].begin(),vec[lon].end(),hash);
}
int main()
{
	int num;
	scanf("%d",&num);
	string str;
	cin>>str;
	for(int i=0;i<num;i++)
	{
		string zan;
		cin>>zan;
		ll hash=0;
		for(int j=0;j<zan.size();j++)
		{
			hash*=mot;
			hash+=zan[j];
		}
		vec[zan.size()].push_back(hash);
	}
	for(int i=0;i<21;i++)
	{
		sort(vec[i].begin(),vec[i].end());
	}
	for(int i=1;i<=min(20,int(str.size()));i++)
	{
		ll hash=0;
		ll jou=1;
		for(int j=0;j<i;j++)
		{
			hash*=mot;
			hash+=str[j];
			jou*=mot;
		}
		if(han(hash,i))
		{
			poi[0]=max(poi[0],i-1);
		}
		for(int j=i;j<str.size();j++)
		{
			hash*=mot;
			hash+=str[j];
			hash-=jou*str[j-i];
			if(han(hash,i))
			{
				poi[j-i+1]=max(poi[j-i+1],j);
			}
		}
	}
	if(str.size()==1)
	{
		printf("1\n");
		return 0;
	}
	int ret=0;
	int now=0;
	for(int i=1;i<str.size();i++)
	{
		poi[i]=max(poi[i],poi[i-1]);
	}
	for(;;)
	{
		if(now==str.size()-1)
		{
			break;
		}
		now=poi[now];
		ret++;
	}
	printf("%d\n",ret);
}

Deciphering こういうちょっとした発想ゲー好き

#include<stdio.h>
#include<vector>
#include<algorithm>
#include<string>
#include<iostream>
using namespace std;
vector<int>moj[26];
bool map[26][26];
int dp[300000];
int mod=10000000;
int main()
{
	int num;
	scanf("%d",&num);
	string str;
	for(int i=0;i<num;i++)
	{
		char zan;
		scanf(" %c",&zan);
		str.push_back(zan);
	}
	for(int i=0;i<str.size();i++)
	{
		if(moj[str[i]-'A'].empty())
		{
			dp[i]=1;
		}
		moj[str[i]-'A'].push_back(i);
	}
	for(int i=0;i<26;i++)
	{
		reverse(moj[i].begin(),moj[i].end());
	}
	int kin;
	scanf("%d",&kin);
	for(int i=0;i<26;i++)
	{
		for(int j=0;j<26;j++)
		{
			map[i][j]=true;
		}
	}
	for(int i=0;i<kin;i++)
	{
		char za,zb;
		scanf(" %c %c",&za,&zb);
		map[za-'A'][zb-'A']=false;
	}
	int sum=0;
	for(int i=0;i<num;i++)
	{
		moj[str[i]-'A'].pop_back();
		for(int j=0;j<26;j++)
		{
			if(map[str[i]-'A'][j]&&(moj[j].size()!=0))
			{
				dp[moj[j][moj[j].size()-1]]+=dp[i];
				dp[moj[j][moj[j].size()-1]]%=mod;
			}
		}
		sum+=dp[i];
		sum%=mod;
	}
	printf("%d\n",sum);
}

Distribution オーダーもっと悪くても間に合うらしいけどlog解思いついたのでわざとlogでやっている。爆速

#include<stdio.h>
#include<vector>
#include<algorithm>
#include<set>
using namespace std;
typedef pair<int,int>pii;
set<int>ko[10000];
int par[10000];
int cost[10000];
bool flag[10000];
int main()
{
	int num,dis;
	scanf("%d%d",&num,&dis);
	int sum=0;
	for(int i=0;i<num;i++)
	{
		int za,zb;
		scanf("%d%d",&za,&zb);
		za--;
		cost[i]=zb;
		par[i]=za;
		sum+=zb;
		if(za!=-1)
		{
			ko[za].insert(i);
		}
		else
		{
			par[i]=0;
		}
	}
	set<pii>se;
	fill(flag,flag+num,true);
	int siz=0;
	for(int i=0;i<num;i++)
	{
		if(ko[i].empty()&&flag[i])
		{
			int nowcost=cost[i];
			int now=par[i];
			int bef=i;
			for(;;)
			{
				if(ko[now].size()!=1||now==0)
				{
					ko[now].erase(bef);
					par[i]=now;
					ko[now].insert(i);
					break;
				}
				flag[now]=false;
				nowcost+=cost[now];
				bef=par[bef];
				now=par[now];
			}
			cost[i]=nowcost;
			se.insert(make_pair(nowcost,i));
			siz++;
		}
	}
	for(int p=0;p<siz-dis;p++)
	{
		set<pii>::iterator it=se.begin();
		pii zan=*it;
		se.erase(it);
		sum-=zan.first;
		ko[par[zan.second]].erase(zan.second);
		if(ko[par[zan.second]].size()==1&&par[zan.second]!=0)
		{
			set<int>::iterator it2=ko[par[zan.second]].begin();
			int zan2=*it2;
			if(ko[zan2].empty())
			{
				se.erase(make_pair(cost[zan2],zan2));
				int bef=zan2;
				int now=par[zan2];
				int nowcost=cost[zan2];
				for(;;)
				{
					if(ko[now].size()!=1)
					{
						ko[now].erase(bef);
						par[zan2]=now;
						ko[now].insert(zan2);
						break;
					}
					bef=par[bef];
					nowcost+=cost[now];
					now=par[now];
				}
				se.insert(make_pair(nowcost,zan2));
				cost[zan2]=nowcost;
			}
		}
	}
	printf("%d\n",sum);
}

Territory 同じようなコード何回も書くの防ぐのどうすればいいんだろう

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
typedef pair<int,int>pii;
typedef pair<pii,int>pi3;
typedef long long ll;
int main()
{
	vector<pi3>vec;
	int nx=0,ny=0;
	for(;;)
	{
		char zan;
		scanf(" %c",&zan);
		if(zan=='Q')
		{
			break;
		}
		if(zan=='N')
		{
			vec.push_back(make_pair(make_pair(nx,ny),0));
			vec.push_back(make_pair(make_pair(nx-1,ny),2));
			nx--;
		}
		if(zan=='W')
		{
			vec.push_back(make_pair(make_pair(nx,ny),1));
			vec.push_back(make_pair(make_pair(nx,ny-1),3));
			ny--;
		}
		if(zan=='S')
		{
			vec.push_back(make_pair(make_pair(nx,ny),2));
			vec.push_back(make_pair(make_pair(nx+1,ny),0));
			nx++;
		}
		if(zan=='E')
		{
			vec.push_back(make_pair(make_pair(nx,ny),3));
			vec.push_back(make_pair(make_pair(nx,ny+1),1));
			ny++;
		}
	}
	sort(vec.begin(),vec.end());
	if(vec.empty())
	{
		printf("0\n");
		return 0;
	}/*
	for(int i=0;i<vec.size();i++)
	{
		printf("debug:%d %d %d\n",vec[i].first.first,vec[i].first.second,vec[i].second);
	}*/
	nx=vec[0].first.first;
	ny=vec[0].first.second;
	int nh=vec[0].second;
	bool han=false;
	vector<pii>ans;
	for(;;)
	{
		//printf("%d %d %d\n",nx,ny,nh);
		if(make_pair(make_pair(nx,ny),nh)==vec[0])
		{
			if(han)
			{
				break;
			}
			han=true;
		}
		if(nh==0)
		{
			ans.push_back(make_pair(nx-1,ny));
		}
		if(nh==2)
		{
			ans.push_back(make_pair(nx,ny));
		}
		if(nh==0)
		{
			if(lower_bound(vec.begin(),vec.end(),make_pair(make_pair(nx-1,ny),3))!=upper_bound(vec.begin(),vec.end(),make_pair(make_pair(nx-1,ny),3)))
			{
				nx--;
				nh=3;
				continue;
			}
			if(lower_bound(vec.begin(),vec.end(),make_pair(make_pair(nx-1,ny),0))!=upper_bound(vec.begin(),vec.end(),make_pair(make_pair(nx-1,ny),0)))
			{
				nx--;
				nh=0;
				continue;
			}
			if(lower_bound(vec.begin(),vec.end(),make_pair(make_pair(nx-1,ny),1))!=upper_bound(vec.begin(),vec.end(),make_pair(make_pair(nx-1,ny),1)))
			{
				nx--;
				nh=1;
				continue;
			}
			if(lower_bound(vec.begin(),vec.end(),make_pair(make_pair(nx-1,ny),2))!=upper_bound(vec.begin(),vec.end(),make_pair(make_pair(nx-1,ny),2)))
			{
				nx--;
				nh=2;
				continue;
			}
		}
		if(nh==1)
		{
			if(lower_bound(vec.begin(),vec.end(),make_pair(make_pair(nx,ny-1),0))!=upper_bound(vec.begin(),vec.end(),make_pair(make_pair(nx,ny-1),0)))
			{
				ny--;
				nh=0;
				continue;
			}
			if(lower_bound(vec.begin(),vec.end(),make_pair(make_pair(nx,ny-1),1))!=upper_bound(vec.begin(),vec.end(),make_pair(make_pair(nx,ny-1),1)))
			{
				ny--;
				nh=1;
				continue;
			}
			if(lower_bound(vec.begin(),vec.end(),make_pair(make_pair(nx,ny-1),2))!=upper_bound(vec.begin(),vec.end(),make_pair(make_pair(nx,ny-1),2)))
			{
				ny--;
				nh=2;
				continue;
			}
			if(lower_bound(vec.begin(),vec.end(),make_pair(make_pair(nx,ny-1),3))!=upper_bound(vec.begin(),vec.end(),make_pair(make_pair(nx,ny-1),3)))
			{
				ny--;
				nh=3;
				continue;
			}
		}
		if(nh==2)
		{
			if(lower_bound(vec.begin(),vec.end(),make_pair(make_pair(nx+1,ny),1))!=upper_bound(vec.begin(),vec.end(),make_pair(make_pair(nx+1,ny),1)))
			{
				nx++;
				nh=1;
				continue;
			}
			if(lower_bound(vec.begin(),vec.end(),make_pair(make_pair(nx+1,ny),2))!=upper_bound(vec.begin(),vec.end(),make_pair(make_pair(nx+1,ny),2)))
			{
				nx++;
				nh=2;
				continue;
			}
			if(lower_bound(vec.begin(),vec.end(),make_pair(make_pair(nx+1,ny),3))!=upper_bound(vec.begin(),vec.end(),make_pair(make_pair(nx+1,ny),3)))
			{
				nx++;
				nh=3;
				continue;
			}
			if(lower_bound(vec.begin(),vec.end(),make_pair(make_pair(nx+1,ny),0))!=upper_bound(vec.begin(),vec.end(),make_pair(make_pair(nx+1,ny),0)))
			{
				nx++;
				nh=0;
				continue;
			}
		}
		if(nh==3)
		{
			if(lower_bound(vec.begin(),vec.end(),make_pair(make_pair(nx,ny+1),2))!=upper_bound(vec.begin(),vec.end(),make_pair(make_pair(nx,ny+1),2)))
			{
				ny++;
				nh=2;
				continue;
			}
			if(lower_bound(vec.begin(),vec.end(),make_pair(make_pair(nx,ny+1),3))!=upper_bound(vec.begin(),vec.end(),make_pair(make_pair(nx,ny+1),3)))
			{
				ny++;
				nh=3;
				continue;
			}
			if(lower_bound(vec.begin(),vec.end(),make_pair(make_pair(nx,ny+1),0))!=upper_bound(vec.begin(),vec.end(),make_pair(make_pair(nx,ny+1),0)))
			{
				ny++;
				nh=0;
				continue;
			}
			if(lower_bound(vec.begin(),vec.end(),make_pair(make_pair(nx,ny+1),1))!=upper_bound(vec.begin(),vec.end(),make_pair(make_pair(nx,ny+1),1)))
			{
				ny++;
				nh=1;
				continue;
			}
		}
	}
	sort(ans.begin(),ans.end());
	ll sum=0;
	int now=-100000000;
	bool gk=false;/*
	for(int i=0;i<ans.size();i++)
	{
		printf("%d %d\n",ans[i].first,ans[i].second);
	}*/
	for(int i=0;i<ans.size();i++)
	{
		if(now!=ans[i].first)
		{
			gk=true;
			now=ans[i].first;
		}
		else
		{
			if(gk)
			{
				sum+=ans[i].second-ans[i-1].second;
				gk=false;
			}
			else
			{
				gk=true;
			}
		}
	}
	printf("%lld\n",sum);
}

Guess them all にぶたん。最初の0hitの例の構成は乱数で適当にやる(1/eくらいの確率で0hitなので常勝)

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
int hai[100];
int main()
{
	int num;
	scanf("%d",&num);
	vector<int>zer;
	for(;;)
	{
		for(int i=0;i<num;i++)
		{
			int zan=(rand()%num)+1;
			printf("%d\n",zan);
			zer.push_back(zan);
		}
		fflush(stdout);
		int ret;
		scanf("%d",&ret);
		if(ret==0)
		{
			break;
		}
		if(ret==num)
		{
			return 0;
		}
		zer.clear();
	}
	vector<int>jun;
	int rui[100];
	int ans[100];
	for(int i=0;i<num;i++)
	{
		rui[i]=i;
	}
	for(int i=0;i<num;i++)
	{
		int beg=0,end=num-i-1;
		for(;;)
		{
			int med=(beg+end)/2;
			for(int j=0;j<num;j++)
			{
				if(j<=rui[med])
				{
					printf("%d\n",i+1);
				}
				else
				{
					printf("%d\n",zer[j]);
				}
			}
			fflush(stdout);
			int ret;
			scanf("%d",&ret);
			if(ret==0)
			{
				beg=med+1;
			}
			else
			{
				end=med;
			}
			if(ret==num)
			{
				return 0;
			}
			if(beg==end)
			{
				ans[rui[beg]]=i+1;
				for(int k=beg;k<num-i;k++)
				{
					rui[k]=rui[k+1];
				}
				break;
			}
		}
	}
	for(int i=0;i<num;i++)
	{
		printf("%d\n",ans[i]);
	}
	fflush(stdout);
}

Shiritori coutを消すゲーム

#include<stdio.h>
#include<vector>
#include<algorithm>
#include<string>
#include<iostream>
using namespace std;
vector<string>map[100][100];
int ein[100];
int eout[100];
vector<int>topo;
bool flag[100];
int ban[100];
vector<int>to[100];
void dfs(int node)
{
	if(flag[node])
	{
		return;
	}
	flag[node]=true;
	for(int i=0;i<100;i++)
	{
		if(!flag[i]&&map[node][i].size()!=0)
		{
			dfs(i);
		}
	}
	topo.push_back(node);
}
void rdfs(int node,int b)
{
	if(flag[node])
	{
		return;
	}
	flag[node]=true;
	for(int i=0;i<100;i++)
	{
		if(!flag[i]&&map[i][node].size()!=0)
		{
			rdfs(i,b);
		}
	}
	ban[node]=b;
	to[b].push_back(node);
}
void scc()
{
	topo.clear();
	for(int i=0;i<100;i++)
	{
		to[i].clear();
	}
	fill(flag,flag+100,false);
	for(int i=0;i<100;i++)
	{
		if(!flag[i]&&(ein[i]!=0||eout[i]!=0))
		{
			dfs(i);
		}
	}
	fill(flag,flag+100,false);
	int now=0;
	for(int i=topo.size()-1;i>=0;i--)
	{
		if(!flag[topo[i]])
		{
			rdfs(topo[i],now);
			now++;
		}
	}
}
int main()
{
	int num;
	scanf("%d",&num);
	for(int i=0;i<num;i++)
	{
		string zan;
		zan.resize(10);
		for(int j=0;j<10;j++)
		{
			scanf(" %c",&zan[j]);
		}
		ein[(zan[8]-'0')*10+(zan[9]-'0')]++;
		eout[(zan[0]-'0')*10+(zan[1]-'0')]++;
		map[(zan[0]-'0')*10+(zan[1]-'0')][(zan[8]-'0')*10+(zan[9]-'0')].push_back(zan);
	}
	int pl=0,mi=0;
	int st=-1;
	for(int i=0;i<100;i++)
	{
		if(ein[i]!=eout[i])
		{
			if(ein[i]+1==eout[i])
			{
				pl++;
				st=i;
			}
			else
			{
				if(ein[i]==eout[i]+1)
				{
					mi++;
				}
				else
				{
					pl+=2;
					mi+=2;
				}
			}
		}
	}
	if(pl==0&&mi==0)
	{
		for(int i=0;i<100;i++)
		{
			if(eout[i]!=0)
			{
				st=i;
				break;
			}
		}
	}
	fill(flag,flag+100,false);
	dfs(st);
	for(int i=0;i<100;i++)
	{
		if((ein[i]!=0||eout[i]!=0)&&!flag[i])
		{
			pl=2;
			mi=2;
		}
	}
	if(pl>=2||mi>=2)
	{
		printf("impossible\n");
		return 0;
	}
	for(int i=0;i<100;i++)
	{
		for(int j=0;j<100;j++)
		{
			sort(map[i][j].begin(),map[i][j].end());
			reverse(map[i][j].begin(),map[i][j].end());
		}
	}
	scc();
	bool fl=false;
	for(int i=0;i<num;i++)
	{
		if(ein[st]==0)
		{
			string mini="9";
			mini[0]++;
			int nn=-1;
			for(int j=0;j<100;j++)
			{
				if(map[st][j].size()!=0)
				{
					if(mini>map[st][j][map[st][j].size()-1])
					{
						mini=map[st][j][map[st][j].size()-1];
						nn=j;
					}
				}
			}
			string zan=map[st][nn][map[st][nn].size()-1];
			cout<<zan<<endl;
			map[st][nn].pop_back();
			if(map[st][nn].empty())
			{
				scc();
			}
			eout[st]--;
			ein[nn]--;
			st=nn;
		}
		else
		{
			string mini="9";
			mini[0]++;
			int nn=-1;
			for(int j=0;j<100;j++)
			{
				if(ban[j]==ban[st]&&map[st][j].size()!=0)
				{
					if(mini>map[st][j][map[st][j].size()-1])
					{
						mini=map[st][j][map[st][j].size()-1];
						nn=j;
					}
				}
			}
			string zan=map[st][nn][map[st][nn].size()-1];
			for(int p=0;p<10;p++)
			{
				printf("%c",zan[p]);
			}
			printf("\n");
			map[st][nn].pop_back();
			if(map[st][nn].empty())
			{
				scc();
			}
			eout[st]--;
			ein[nn]--;
			st=nn;
		}
	}
}

Apples 動的segtree実装簡単だった

#include<stdio.h>
#include<vector>
#include<algorithm>
#include<set>
using namespace std;
typedef long long ll;
#define SIZE 1073741824LL
class segtree
{
public:
  int seg[7000000];
  int flag[7000000];
  int lko[7000000];
  int rko[7000000];
  int segpt;
  void init()
  {
    fill(lko,lko+7000000,-1);
    fill(rko,rko+7000000,-1);
    segpt=1;
  }
  void makenode(int node,int s)
  {
    if(s==0)
      {
	lko[node]=segpt;
	segpt++;
      }
    else
      {
	rko[node]=segpt;
	segpt++;
      }
  }
  void update(ll beg,ll end,int node,ll lb,ll ub,int num)
  {
    if(ub<beg||end<lb)
      {
	return;
      }
    if(beg<=lb&&ub<=end)
      {
	seg[node]+=num;
	flag[node]+=num;
	return;
      }
    if(lko[node]==-1)
      {
	makenode(node,0);
      }
    if(rko[node]==-1)
      {
	makenode(node,1);
      }
    if(flag[node])
      {
	flag[lko[node]]+=flag[node];
	flag[rko[node]]+=flag[node];
	seg[lko[node]]+=flag[node];
	seg[rko[node]]+=flag[node];
	flag[node]=0;
      }
    update(beg,end,lko[node],lb,(lb+ub)/2,num);
    update(beg,end,rko[node],(lb+ub)/2+1,ub,num);
    seg[node]=max(seg[lko[node]],seg[rko[node]]);
    return;
  }
  ll get(int node,ll lb,ll ub,ll num)
  {
    if(lb==ub)
      {
	return lb;
      }
    if(lko[node]==-1)
      {
	makenode(node,0);
      }
    if(rko[node]==-1)
      {
	makenode(node,1);
      }
    if(flag[node])
      {
	flag[lko[node]]+=flag[node];
	flag[rko[node]]+=flag[node];
	seg[lko[node]]+=flag[node];
	seg[rko[node]]+=flag[node];
	flag[node]=0;
      }
    if(seg[rko[node]]>=num)
      {
	return get(rko[node],(lb+ub)/2+1,ub,num);
      }
    else
      {
	return get(lko[node],lb,(lb+ub)/2,num);
      }
  }
};
segtree tree;
int main()
{
  int query;
  ll dif;
  scanf("%d%lld",&query,&dif);
  multiset<ll>se;
  tree.init();
  for(int p=0;p<query;p++)
    {
      char za;
      ll zb;
      scanf(" %c",&za);
      if(za=='E')
	{
	  break;
	}
      scanf("%lld",&zb);
      if(za=='A')
	{
	  tree.update(zb,min(SIZE-1,zb+dif),0,0LL,SIZE-1LL,1);
	  se.insert(zb);
	}
      else
	{
	  if(tree.seg[0]<zb)
	    {
	      printf("NO\n");
	      fflush(stdout);
	    }
	  else
	    {
	      ll ret=tree.get(0,0LL,SIZE-1,zb);
	      multiset<ll>::iterator it=se.upper_bound(ret);
	      it--;
	      vector<ll>ans;
	      for(int i=0;i<zb;i++)
		{
		  ans.push_back(*it);
		  tree.update(*it,min(SIZE-1,*it+dif),0,0LL,SIZE-1,-1);
		  se.erase(it--);
		}
	      reverse(ans.begin(),ans.end());
	      for(int i=0;i<ans.size();i++)
		{
		  if(i!=0)
		    {
		      printf(" ");
		    }
		  printf("%lld",ans[i]);
		}
	      printf("\n");
	      fflush(stdout);
	    }
	}
    }
}

Fortune telling 閉区間でもできます

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
class segtree
{
public:
	ll seg[524288];
	int flip[524288];
	ll sper[524288];
	void init(vector<int>vec)
	{
		for(int i=0;i<524288;i++)
		{
			seg[i]=0;
			flip[i]=0;
		}
		for(int i=262144;i<262144+vec.size()-1;i++)
		{
			sper[i]=vec[i-262144+1]-vec[i-262144];
		}
		for(int i=262144+vec.size();i<524288;i++)
		{
			sper[i]=0;
		}
		for(int i=262143;i>0;i--)
		{
			sper[i]=sper[i*2]+sper[i*2+1];
		}
	}
	ll update(int beg,int end,int node,int lb,int ub)
	{
		if(ub<beg||end<lb)
		{
			return seg[node];
		}
		if(beg<=lb&&ub<=end)
		{
			flip[node]^=1;
			return seg[node]=sper[node]-seg[node];
		}
		if(flip[node])
		{
			flip[node*2]^=1;
			seg[node*2]=sper[node*2]-seg[node*2];
			flip[node*2+1]^=1;
			seg[node*2+1]=sper[node*2+1]-seg[node*2+1];
			flip[node]=0;
		}
		return seg[node]=update(beg,end,node*2,lb,lb+sper[node*2]-1)+update(beg,end,node*2+1,lb+sper[node*2],ub);
	}
	ll get()
	{
		return seg[1];
	}
};
segtree tree;
typedef pair<int,int>pii;
typedef pair<int,pii>pi3;
int main()
{
	int mx,my,query;
	scanf("%d%d%d",&mx,&my,&query);
	vector<pi3>vec;
	vec.push_back(make_pair(0,make_pair(-1,-1)));
	vector<int>zat;
	for(int i=0;i<query;i++)
	{
		int za,zb,zc,zd;
		scanf("%d%d%d%d",&za,&zb,&zc,&zd);
		zc--;
		zd--;
		vec.push_back(make_pair(za-1,make_pair(zc,zd)));
		vec.push_back(make_pair(zb,make_pair(zc,zd)));
		zat.push_back(zc);
		zat.push_back(zd+1);
	}
	zat.push_back(0);
	zat.push_back(my);
	vec.push_back(make_pair(mx,make_pair(2000000000,2000000000)));
	sort(vec.begin(),vec.end());
	sort(zat.begin(),zat.end());
	vector<int>zv;
	int now=-1;
	for(int i=0;i<zat.size();i++)
	{
		if(now!=zat[i])
		{
			zv.push_back(zat[i]);
			now=zat[i];
		}
	}
	zat=zv;
	tree.init(zat);
	ll ret=0;
	for(int i=1;i<vec.size();i++)
	{
		ret+=tree.get()*(vec[i].first-vec[i-1].first);
		if(i!=vec.size()-1)
		{
			tree.update(vec[i].second.first,vec[i].second.second,1,0,zat[zat.size()-1]);
		}
	}
	ll men=mx;
	men*=my;
	printf("%lld\n",men-ret);
}

Rotate 4つ持っておいて張り替える

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
char map[4020000];
int down[4020000];
int right[4020000];
int todown[4][1002];
int toright[4][1002];
int main()
{
	int num,query;
	scanf("%d%d",&num,&query);
	for(int i=0;i<(num+2)*(num+2);i++)
	{
		map[i]=' ';
		down[i]=i;
		right[i]=i;
	}
	for(int i=1;i<=num;i++)
	{
		for(int j=1;j<=num;j++)
		{
			char zan;
			scanf(" %c",&zan);
			map[i*(num+2)+j]=zan;
			map[(num+2)*(num+2)+(num+1-j)*(num+2)+i]=zan;
			map[(num+2)*(num+2)*2+(num+1-i)*(num+2)+(num+1-j)]=zan;
			map[(num+2)*(num+2)*3+j*(num+2)+(num+1-i)]=zan;
		}
	}
	for(int i=0;i<4;i++)
	{
		for(int j=0;j<num+1;j++)
		{
			for(int k=0;k<num+2;k++)
			{
				down[i*(num+2)*(num+2)+j*(num+2)+k]=i*(num+2)*(num+2)+(j+1)*(num+2)+k;
				right[i*(num+2)*(num+2)+k*(num+2)+j]=i*(num+2)*(num+2)+k*(num+2)+(j+1);
			}
		}
	}
	for(int i=0;i<4;i++)
	{
		for(int j=0;j<num+2;j++)
		{
			todown[i][j]=i*(num+2)*(num+2)+j;
			toright[i][j]=i*(num+2)*(num+2)+j*(num+2);
		}
	}
	for(int i=0;i<query;i++)
	{
		int za,zb,zc;
		scanf("%d%d%d",&za,&zb,&zc);
		int now[8];
		now[0]=now[4]=toright[0][za];
		now[1]=now[5]=toright[1][num+1-zb-zc+1];
		now[2]=now[6]=toright[2][num+1-za-zc+1];
		now[3]=now[7]=toright[3][zb];
		for(int j=0;j<zb-1;j++)
		{
			now[0]=right[now[0]];
		}
		for(int j=0;j<za-1;j++)
		{
			now[1]=right[now[1]];
		}
		for(int j=0;j<num+1-zb-zc+1-1;j++)
		{
			now[2]=right[now[2]];
		}
		for(int j=0;j<num+1-za-zc+1-1;j++)
		{
			now[3]=right[now[3]];
		}
		for(int j=0;j<zb+zc-1;j++)
		{
			now[4]=right[now[4]];
		}
		for(int j=0;j<za+zc-1;j++)
		{
			now[5]=right[now[5]];
		}
		for(int j=0;j<num+1-zb-zc+1+zc-1;j++)
		{
			now[6]=right[now[6]];
		}
		for(int j=0;j<num+1-za-zc+1+zc-1;j++)
		{
			now[7]=right[now[7]];
		}
		for(int j=0;j<zc;j++)
		{
			int t=right[now[0]];
			right[now[0]]=right[now[1]];
			right[now[1]]=right[now[2]];
			right[now[2]]=right[now[3]];
			right[now[3]]=t;
			t=right[now[4]];
			right[now[4]]=right[now[7]];
			right[now[7]]=right[now[6]];
			right[now[6]]=right[now[5]];
			right[now[5]]=t;
			for(int k=0;k<8;k++)
			{
				now[k]=down[now[k]];
			}
		}
		now[0]=now[4]=todown[0][zb];
		now[1]=now[5]=todown[1][za];
		now[2]=now[6]=todown[2][num+1-zb-zc+1];
		now[3]=now[7]=todown[3][num+1-za-zc+1];
		for(int j=0;j<za-1;j++)
		{
			now[0]=down[now[0]];
		}
		for(int j=0;j<num+1-zb-zc+1-1;j++)
		{
			now[1]=down[now[1]];
		}
		for(int j=0;j<num+1-za-zc+1-1;j++)
		{
			now[2]=down[now[2]];
		}
		for(int j=0;j<zb-1;j++)
		{
			now[3]=down[now[3]];
		}
		for(int j=0;j<za-1+zc;j++)
		{
			now[4]=down[now[4]];
		}
		for(int j=0;j<num+1-zb-zc+1-1+zc;j++)
		{
			now[5]=down[now[5]];
		}
		for(int j=0;j<num+1-za-zc+1-1+zc;j++)
		{
			now[6]=down[now[6]];
		}
		for(int j=0;j<zb-1+zc;j++)
		{
			now[7]=down[now[7]];
		}
		for(int j=0;j<zc;j++)
		{
			int t=down[now[0]];
			down[now[0]]=down[now[1]];
			down[now[1]]=down[now[2]];
			down[now[2]]=down[now[3]];
			down[now[3]]=t;
			t=down[now[4]];
			down[now[4]]=down[now[7]];
			down[now[7]]=down[now[6]];
			down[now[6]]=down[now[5]];
			down[now[5]]=t;
			for(int k=0;k<8;k++)
			{
				now[k]=right[now[k]];
			}
		}
	}
	for(int i=1;i<=num;i++)
	{
		int now=toright[0][i];
		for(int j=1;j<=num;j++)
		{
			now=right[now];
			printf("%c",map[now]);
		}
		printf("\n");
	}
}

Sokoban 本番でこれ出たら解法わかっても実装できる気がしない

#include<stdio.h>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
typedef pair<pii,int>pi3;
int map[1002][1002];
int lowlink[1002][1002];
int topo[1002][1002];
int rev[1002][1002];
pii par[1002][1002];
bool flag[1002][1002];
bool isgo[1002][1002][4];
int kosize[1002][1002][4];
bool bfsflag[1002][1002][4];
int dx[4]={-1,0,1,0};
int dy[4]={0,-1,0,1};
int nowtopo=0,nowrev=0;
int dfs(int nodex,int nodey)
{
  if(flag[nodex][nodey])
    {
      return 0;
    }
  flag[nodex][nodey]=true;
  topo[nodex][nodey]=nowtopo++;
  int ret=0;
  for(int i=0;i<4;i++)
    {
      if(map[nodex+dx[i]][nodey+dy[i]]==0)
	{
	  if(!flag[nodex+dx[i]][nodey+dy[i]])
	    {
	      kosize[nodex][nodey][i]=dfs(nodex+dx[i],nodey+dy[i]);
	      isgo[nodex][nodey][i]=true;
	      //printf("%d %d  %d %d\n",nodex,nodey,nodex+dx[i],nodey+dy[i]);
	      ret+=kosize[nodex][nodey][i];
	      par[nodex+dx[i]][nodey+dy[i]]=make_pair(nodex,nodey);
	    }
	}
    }
  rev[nodex][nodey]=nowrev++;
  return ret+1;
}
bool isback(int nodex,int nodey,int fo)
{
  return map[nodex+dx[fo]][nodey+dy[fo]]==0&&(!isgo[nodex+dx[fo]][nodey+dy[fo]][(fo+2)%4])&&topo[nodex][nodey]>topo[nodex+dx[fo]][nodey+dy[fo]];
}
bool isrevback(int nodex,int nodey,int fo)
{
  return isback(nodex+dx[fo],nodey+dy[fo],(fo+2)%4);
}
bool islow(int nodex,int nodey,int nodexf,int nodeyf)
{
  return (topo[nodex][nodey]<topo[nodexf][nodeyf]&&rev[nodexf][nodeyf]<rev[nodex][nodey]);
}
int getlink(int nodex,int nodey,int fo)
{
  if(isgo[nodex][nodey][fo])
    {
      return fo;
    }
  for(int i=0;i<4;i++)
    {
      if(isgo[nodex][nodey][i])
	{
	  if(islow(nodex+dx[i],nodey+dy[i],nodex+dx[fo],nodey+dy[fo]))
	    {
	      return i;
	    }
	}
    }
  return -1;
}
int calclowlink(int nodex,int nodey)
{
  int minilink=topo[nodex][nodey];
  for(int i=0;i<4;i++)
    {
      if(isgo[nodex][nodey][i])
	{
	  minilink=min(minilink,calclowlink(nodex+dx[i],nodey+dy[i]));
	}
      if(isback(nodex,nodey,i))
	{
	  minilink=min(minilink,topo[nodex+dx[i]][nodey+dy[i]]);
	}
    }
  return lowlink[nodex][nodey]=minilink;
}
bool isunited(int nodex,int nodey,int fo1,int fo2)
{
  if(islow(nodex,nodey,nodex+dx[fo2],nodey+dy[fo2]))
    {
      swap(fo1,fo2);
    }
  if(islow(nodex,nodey,nodex+dx[fo2],nodey+dy[fo2]))
    {
      //printf("lowlow\n");
      int link1=getlink(nodex,nodey,fo1),link2=getlink(nodex,nodey,fo2);
      if(link1==link2)
	{
	  return true;
	}
      return lowlink[nodex+dx[link1]][nodey+dy[link1]]<topo[nodex][nodey]&&lowlink[nodex+dx[link2]][nodey+dy[link2]]<topo[nodex][nodey];
    }
  if(islow(nodex,nodey,nodex+dx[fo1],nodey+dy[fo1]))
    {
      //printf("lowup\n");
      int link=getlink(nodex,nodey,fo1);
      return lowlink[nodex+dx[link]][nodey+dy[link]]<topo[nodex][nodey];
    }
  //printf("upup\n");
  return true;
}
int getsize(int nodex,int nodey,int fo)
{
  int link=getlink(nodex,nodey,fo);
  if(link!=-1)
    {
      if(bfsflag[nodex][nodey][link])
	{
	  return 0;
	}
      bfsflag[nodex][nodey][link]=true;
      return kosize[nodex][nodey][link];
    }
  if(par[nodex][nodey]==make_pair(nodex+dx[fo],nodey+dy[fo])&&(!bfsflag[nodex][nodey][fo]))
    {
      int ret=nowtopo-2;
      for(int i=0;i<4;i++)
	{
	  ret-=kosize[nodex][nodey][i];
	}
      bfsflag[nodex][nodey][fo]=true;
      return ret;
    }
  return 0;
}
int main()
{
  int mx,my;
  scanf("%d%d",&mx,&my);
  int sx,sy;
  for(int i=0;i<=mx+1;i++)
    {
      for(int j=0;j<=my+1;j++)
	{
	  map[i][j]=1;
	  flag[i][j]=false;
	  for(int k=0;k<4;k++)
	    {
	      bfsflag[i][j][k]=false;
	    }
	  lowlink[i][j]=1000000000;
	}
    }
  for(int i=0;i<mx;i++)
    {
      for(int j=0;j<my;j++)
	{
	  char zan;
	  scanf(" %c",&zan);
	  if(zan=='.')
	    {
	      map[i+1][j+1]=0;
	    }
	  if(zan=='X')
	    {
	      sx=i+1;
	      sy=j+1;
	      map[i+1][j+1]=0;
	    }
	}
    }
  dfs(sx,sy);
  calclowlink(sx,sy);/*
  for(int i=0;i<mx+2;i++)
    {
      for(int j=0;j<my+2;j++)
	{
	  printf("%d ",topo[i][j]);
	}
      printf("\n");
    }
  for(int i=0;i<mx+2;i++)
    {
      for(int j=0;j<my+2;j++)
	{
	  printf("%11d",lowlink[i][j]);
	}
      printf("\n");
      }*/
  queue<pi3>que;
  for(int i=0;i<4;i++)
    {
      if(map[sx+dx[i]][sy+dy[i]]==0)
	{
	  que.push(make_pair(make_pair(sx,sy),i));
	}
    }
  ll ans=0;
  for(;;)
    {
      if(que.empty())
	{
	  break;
	}
      pi3 zan=que.front();
      que.pop();
      if(bfsflag[zan.first.first][zan.first.second][zan.second])
	{
	  continue;
	}
      //printf("%d %d %d\n",zan.first.first,zan.first.second,zan.second);
      for(int i=0;i<4;i++)
	{
	  if(map[zan.first.first+dx[i]][zan.first.second+dy[i]]==0&&map[zan.first.first+dx[zan.second]][zan.first.second+dy[zan.second]]==0)
	    {
	      //printf("%d\n",i);
	      if(isunited(zan.first.first,zan.first.second,i,zan.second))
		{
		  if(!bfsflag[zan.first.first][zan.first.second][i])
		    {
		      if(zan.first!=make_pair(sx,sy))
			{
			  ans+=getsize(zan.first.first,zan.first.second,i);
			}
		      //printf("ok %d\n",ans);
		    }
		  if(map[zan.first.first+2*dx[i]][zan.first.second+2*dy[i]]==0)
		    {
		      que.push(make_pair(make_pair(zan.first.first+dx[i],zan.first.second+dy[i]),i));
		    }
		}
	    }
	}
      bfsflag[zan.first.first][zan.first.second][zan.second]=true;
    }
  printf("%lld\n",ans);
}