「CF534X」Codeforces Round #298 (Div. 2)

#include<set>
#include<map>
#include<ctime>
#include<queue>
#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define inf 1000000000
#define ll long long 
using namespace std;
int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int n;
int main()
{
	n=read();
	if(n==2)
	{
		puts("1");puts("1");
	}
	else if(n==3)
	{
		puts("2");
		puts("1 3");
	}
	else 
	{
		printf("%d\n",n);
		if(n&1)printf("%d ",n/2+1);
		for(int i=1;i<=n/2;i++)
			if(n&1)printf("%d %d ",i,n-i+1);
			else printf("%d %d ",n/2+i,i);
		return 0;
	}
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

#include<set>

#include<map>

#include<ctime>

#include<queue>

#include<cmath>

#include<cstdio>

#include<vector>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define inf 1000000000

#define ll long long

using namespace std;

int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n;

int main()

{

n=read();

if(n==2)

{

puts("1");puts("1");

}

else if(n==3)

{

puts("2");

puts("1 3");

}

else

{

printf("%d\n",n);

if(n&1)printf("%d ",n/2+1);

for(int i=1;i<=n/2;i++)

if(n&1)printf("%d %d ",i,n-i+1);

else printf("%d %d ",n/2+i,i);

return 0;

}

#include<set>
#include<map>
#include<ctime>
#include<queue>
#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define inf 1000000000
#define ll long long 
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int a,b,t,d;
int f[105][1050];
int main()
{
    a=read();b=read();
    t=read();d=read();
    memset(f,-1,sizeof(f));
    f[0][a]=0;
    for(int i=0;i<t-1;i++)
        for(int j=0;j<=1000;j++)
            if(f[i][j]!=-1)
                for(int k=0;k<=d;k++)
                {
                    f[i+1][j+k]=max(f[i+1][j+k],f[i][j]+j);
                    if(j>=k)f[i+1][j-k]=max(f[i+1][j-k],f[i][j]+j);
                }
    printf("%d\n",f[t-1][b]+b);
    return 0;
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

#include<set>

#include<map>

#include<ctime>

#include<queue>

#include<cmath>

#include<cstdio>

#include<vector>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define inf 1000000000

#define ll long long

using namespace std;

int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int a,b,t,d;

int f[105][1050];

int main()

{

a=read();b=read();

t=read();d=read();

memset(f,-1,sizeof(f));

f[0][a]=0;

for(int i=0;i<t-1;i++)

for(int j=0;j<=1000;j++)

if(f[i][j]!=-1)

for(int k=0;k<=d;k++)

{

f[i+1][j+k]=max(f[i+1][j+k],f[i][j]+j);

if(j>=k)f[i+1][j-k]=max(f[i+1][j-k],f[i][j]+j);

}

printf("%d\n",f[t-1][b]+b);

return 0;

}

#include<set>
#include<map>
#include<ctime>
#include<queue>
#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define inf 1000000000
#define ll long long 
using namespace std;
ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n;
ll d[200005],A,sum;
int main()
{
    n=read();A=read();
    for(int i=1;i<=n;i++)d[i]=read();
    for(int i=1;i<=n;i++)sum+=d[i];
    for(int i=1;i<=n;i++)
    {
        ll mn=A-(sum-d[i]),mx=A-n+1;
		int t1=mn-1,t2=d[i]-mx;
		if(t1<0)t1=0;if(t2<0)t2=0;
        printf("%d ",t1+t2);
    }
    return 0;
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

#include<set>

#include<map>

#include<ctime>

#include<queue>

#include<cmath>

#include<cstdio>

#include<vector>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define inf 1000000000

#define ll long long

using namespace std;

ll read()

{

ll x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n;

ll d[200005],A,sum;

int main()

{

n=read();A=read();

for(int i=1;i<=n;i++)d[i]=read();

for(int i=1;i<=n;i++)sum+=d[i];

for(int i=1;i<=n;i++)

{

ll mn=A-(sum-d[i]),mx=A-n+1;

int t1=mn-1,t2=d[i]-mx;

if(t1<0)t1=0;if(t2<0)t2=0;

printf("%d ",t1+t2);

}

return 0;

}

#include<set>
#include<map>
#include<ctime>
#include<queue>
#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define inf 1000000000
#define ll long long 
using namespace std;
ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,now,top;
int a[200005],ans[200005];
vector<int> c[200005];
int main()
{
    n=read();
    for(int i=1;i<=n;i++)a[i]=read();
    for(int i=1;i<=n;i++)c[a[i]].push_back(i);
    while(top<n)
    {
        while(!c[now].size())
        {
            now-=3;
            if(now<0){puts("Impossible");return 0;}
        }
        ans[++top]=c[now].back();
        c[now].pop_back();
        now++;
    }
    puts("Possible");
    for(int i=1;i<=top;i++)printf("%d ",ans[i]);
    return 0;
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

#include<set>

#include<map>

#include<ctime>

#include<queue>

#include<cmath>

#include<cstdio>

#include<vector>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define inf 1000000000

#define ll long long

using namespace std;

ll read()

{

ll x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n,now,top;

int a[200005],ans[200005];

vector<int> c[200005];

int main()

{

n=read();

for(int i=1;i<=n;i++)a[i]=read();

for(int i=1;i<=n;i++)c[a[i]].push_back(i);

while(top<n)

{

while(!c[now].size())

{

now-=3;

if(now<0){puts("Impossible");return 0;}

}

ans[++top]=c[now].back();

c[now].pop_back();

now++;

}

puts("Possible");

for(int i=1;i<=top;i++)printf("%d ",ans[i]);

return 0;

}

#include<set>
#include<map>
#include<ctime>
#include<queue>
#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define inf 1000000000
#define ll long long 
using namespace std;
ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
ll ans;
int n,m,tot;
int a[200005],b[400005];
ll c[200005];
bool check(int l,int r)
{
    for(int i=l+1;i<=r;i++)
        if(a[i]-a[i-1]!=a[l+1]-a[l])return 0;
    return 1;
}
int main()
{
    n=read();
    for(int i=1;i<=n;i++)a[i]=read();
    m=read();
    for(int i=1;i<=m;i++)
    {
        int x=read();
        c[x]++;
        if(x==1||x==n)c[x]++;
    }
    ll mn=inf,mx=0;
    for(int i=1;i<=n;i++)
        mn=min(mn,c[i]),mx=max(mx,c[i]);
    if(mn==mx)
        if(check(1,n))printf("%lld\n",(a[n]-a[1])*mn-(a[2]-a[1]));
        else puts("-1");
    else 
    {
        for(int i=2;i<=n;i++)
            ans+=(a[i]-a[i-1])*min(c[i],c[i-1]);
        printf("%lld\n",ans);
    }
    return 0;
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

#include<set>

#include<map>

#include<ctime>

#include<queue>

#include<cmath>

#include<cstdio>

#include<vector>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define inf 1000000000

#define ll long long

using namespace std;

ll read()

{

ll x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

ll ans;

int n,m,tot;

int a[200005],b[400005];

ll c[200005];

bool check(int l,int r)

{

for(int i=l+1;i<=r;i++)

if(a[i]-a[i-1]!=a[l+1]-a[l])return 0;

return 1;

}

int main()

{

n=read();

for(int i=1;i<=n;i++)a[i]=read();

m=read();

for(int i=1;i<=m;i++)

{

int x=read();

c[x]++;

if(x==1||x==n)c[x]++;

}

ll mn=inf,mx=0;

for(int i=1;i<=n;i++)

mn=min(mn,c[i]),mx=max(mx,c[i]);

if(mn==mx)

if(check(1,n))printf("%lld\n",(a[n]-a[1])*mn-(a[2]-a[1]));

else puts("-1");

else

{

for(int i=2;i<=n;i++)

ans+=(a[i]-a[i-1])*min(c[i],c[i-1]);

printf("%lld\n",ans);

}

return 0;

}

#include<set>
#include<map>
#include<ctime>
#include<queue>
#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define inf 1000000000
#define ll long long 
using namespace std;
ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int bin[30],bin2[10],v[35][35];
int n,m,ed,top;
int a[25],b[25];
vector<int> q[25];
bool f[25][32][161051];
char ans[10][25];
struct data{
    int a,b;
};
void p(int sta)
{
    for(int i=1;i<=n;i++)
        if(sta&bin[i-1])ans[i][top]='*';
        else ans[i][top]='.';
    top--;
}
void dfs(int x,int tot,int sta,bool last)
{
    if(x==n+1)
    {
        q[tot].push_back(sta);
        return;
    }
    dfs(x+1,tot+(!last),sta+bin[x-1],1);
    dfs(x+1,tot,sta,0);
}
bool dfs2(int i,int t1,int k)
{
    f[i][t1][k]=1;
    if(i==m)
    {
        if(k==ed)
        {
            p(t1);return 1;
        }
        return 0;
    }
    for(int y=0;y<q[b[i+1]].size();y++)
    {
        int t2=q[b[i+1]][y];
        int nk=k+v[t1][t2];
        if(nk<=ed)
            if(!f[i+1][t2][nk])
                if(dfs2(i+1,t2,nk)){p(t1);return 1;}
    }
    return 0;
}
int main()
{
    bin[0]=1;for(int i=1;i<30;i++)bin[i]=bin[i-1]<<1;
    bin2[0]=1;for(int i=1;i<10;i++)bin2[i]=bin2[i-1]*11;
    n=read();m=read();
    for(int i=1;i<=n;i++)a[i]=read();
    for(int i=1;i<=m;i++)b[i]=read();
    for(int i=1;i<=n;i++)ed+=a[i]*bin2[i-1];
    dfs(1,0,0,0);
    for(int t1=0;t1<=bin[n]-1;t1++)
        for(int t2=0;t2<=bin[n]-1;t2++)
            for(int l=1;l<=n;l++)
                if((t2&bin[l-1])&&(t1&bin[l-1])==0)v[t1][t2]+=bin2[l-1];
    top=m;
    dfs2(0,0,0);
    for(int i=1;i<=n;i++)printf("%s\n",ans[i]+1);
    return 0;
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

#include<set>

#include<map>

#include<ctime>

#include<queue>

#include<cmath>

#include<cstdio>

#include<vector>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define inf 1000000000

#define ll long long

using namespace std;

ll read()

{

ll x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int bin[30],bin2[10],v[35][35];

int n,m,ed,top;

int a[25],b[25];

vector<int> q[25];

bool f[25][32][161051];

char ans[10][25];

struct data{

int a,b;

};

void p(int sta)

{

for(int i=1;i<=n;i++)

if(sta&bin[i-1])ans[i][top]='*';

else ans[i][top]='.';

top--;

}

void dfs(int x,int tot,int sta,bool last)

{

if(x==n+1)

{

q[tot].push_back(sta);

return;

}

dfs(x+1,tot+(!last),sta+bin[x-1],1);

dfs(x+1,tot,sta,0);

}

bool dfs2(int i,int t1,int k)

{

f[i][t1][k]=1;

if(i==m)

{

if(k==ed)

{

p(t1);return 1;

}

return 0;

}

for(int y=0;y<q[b[i+1]].size();y++)

{

int t2=q[b[i+1]][y];

int nk=k+v[t1][t2];

if(nk<=ed)

if(!f[i+1][t2][nk])

if(dfs2(i+1,t2,nk)){p(t1);return 1;}

}

return 0;

}

int main()

{

bin[0]=1;for(int i=1;i<30;i++)bin[i]=bin[i-1]<<1;

bin2[0]=1;for(int i=1;i<10;i++)bin2[i]=bin2[i-1]*11;

n=read();m=read();

for(int i=1;i<=n;i++)a[i]=read();

for(int i=1;i<=m;i++)b[i]=read();

for(int i=1;i<=n;i++)ed+=a[i]*bin2[i-1];

dfs(1,0,0,0);

for(int t1=0;t1<=bin[n]-1;t1++)

for(int t2=0;t2<=bin[n]-1;t2++)

for(int l=1;l<=n;l++)

if((t2&bin[l-1])&&(t1&bin[l-1])==0)v[t1][t2]+=bin2[l-1];

top=m;

dfs2(0,0,0);

for(int i=1;i<=n;i++)printf("%s\n",ans[i]+1);

return 0;

}

hzwer.com _ Home | http://hzwer.com

分类目录

热门文章

Myfriends

近期评论