NC21531. Hello, Hello and Hello
描述
输入描述
There are multiple test cases. The first line of input is an integer T indicates the number of test cases. For each test case:
The first line contains a ternary string s (1 ≤ |s| ≤ 106).
It is guaranteed that the sum of all |s| does not exceed 106.
输出描述
For each test case, output ``-1'' (without the quotes) if Chiaki can not shuffle the string using the operations described above. Otherwise, output an integer k in the first line -- the minimum number of operations needed. Each of the next k lines output two integers l and r -- denoting an operation.
示例1
输入:
2 001122 000022
输出:
2 4 5 1 1 -1
C++11(clang++ 3.9) 解法, 执行用时: 88ms, 内存消耗: 8036K, 提交时间: 2020-03-14 14:21:34
#include<bits/stdc++.h>
using namespace std;
const int maxn=(int)1e6+1;
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
static char buf[maxn];
scanf("%s",buf);
int c[3]={};
for(int i=0;buf[i];++i)
++c[buf[i]-'0'];
int mx=max(c[0],max(c[1],c[2])),sum=c[0]+c[1]+c[2];
if(mx>sum-mx+1)
{
puts("-1");
}
else
{
int pos=-1,op[3]={},rem[3]={c[0]-1,c[1]-1,c[2]-1};
if(mx==sum-mx+1&&mx>=2)
if(mx==c[0])
{
pos=0;
--rem[0];
}
else if(mx==c[1]&&c[2])
{
pos=1;
--rem[1];
}
while(rem[0]>0||rem[1]>0||rem[2]>0)
{
int low=min(rem[0],min(rem[1],rem[2]));
int i=low==rem[2]?2:(low==rem[0]?0:1);
int j=!i,k=3-i-j;
++op[i];
--rem[j];
--rem[k];
}
printf("%d\n",op[0]+op[1]+op[2]+(pos>=0));
for(int i=0;i<op[0];++i)
{
int x=c[0]+c[1];
printf("%d %d\n",x,x+1);
--c[1];
--c[2];
}
if(pos==1)
{
int x=c[0]+c[1];
printf("%d %d\n",x,x);
--c[1];
}
for(int i=0;i<op[2];++i)
{
int x=c[0];
printf("%d %d\n",x,x+1);
--c[0];
--c[1];
}
assert(c[1]<=1);
for(int i=0;i<op[1];++i)
{
int x=c[0],y=c[0]+c[1];
printf("%d %d\n",x,y+1);
--c[0];
c[1]=0;
--c[2];
}
if(!pos)
{
int x=c[0];
printf("%d %d\n",x,x);
--c[0];
}
}
}
return 0;
}