結果
問題 | No.332 数列をプレゼントに |
ユーザー |
![]() |
提出日時 | 2015-12-27 00:11:17 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 152 ms / 2,000 ms |
コード長 | 2,516 bytes |
コンパイル時間 | 1,089 ms |
コンパイル使用メモリ | 116,556 KB |
実行使用メモリ | 24,576 KB |
最終ジャッジ日時 | 2024-12-24 08:28:14 |
合計ジャッジ時間 | 9,139 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 42 |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System;using System.Collections;using System.Collections.Generic;using System.Linq;using System.Text;using System.Numerics;using BI=System.Numerics.BigInteger;class TEST{static void Main(){Sol mySol =new Sol();mySol.Solve();}}class Sol{public void Solve(){Pair[] AA=new Pair[N];for(int i=0;i<N;i++){AA[i]=new Pair(A[i],i);}Array.Sort(AA,(x,y)=>x.V.CompareTo(y.V));int N1=0;long sum1=0;int Vmax=1000000;for(int i=0;i<N;i++){if(sum1+AA[i].V>=Vmax)break;sum1+=AA[i].V;N1++;}int[] dp=new int[Vmax];for(int i=0;i<Vmax;i++){dp[i]=-1;}dp[0]=-10000000;for(int i=0;i<N1;i++){for(int j=Vmax-1;j>=0;j--){if(dp[j]!=-1 && dp[j+AA[i].V]==-1){dp[j+AA[i].V]=i;}}}int N2=N-N1;long[] Large=new long[1<<N2];Large[0]=0;for(int i=1;i<(1<<N2);i++){int msb=0;for(int j=30;j>=0;j--){if((i>>j)>0){msb=j;break;}}Large[i]=AA[N1+msb].V+Large[(i^(1<<msb))];}Pair[] LA=new Pair[1<<N2];for(int i=0;i<(1<<N2);i++){LA[i]=new Pair(Large[i],i);}Array.Sort(LA,(x,y)=>x.V.CompareTo(y.V));int tail=0;int head=Vmax-1;while(head>=0){if(dp[head]==-1){head--;continue;}while(tail<(1<<N2)-1 && LA[tail].V+head<X)tail++;if(LA[tail].V+head==X){char[] Ans=new char[N];for(int ii=0;ii<N;ii++)Ans[ii]='x';int now=head;while(dp[now]>=0){Ans[AA[dp[now]].Idx]='o';now-=(int)AA[dp[now]].V;}int s=LA[tail].Idx;for(int ii=0;ii<30;ii++){if(((s>>ii)&1)==1){Ans[AA[ii+N1].Idx]='o';}}Console.WriteLine(new String(Ans));return;}head--;}Console.WriteLine("No");}class Pair{public long V;public int Idx;public Pair(long v,int i){V=v;Idx=i;}}long[] A;int N;long X;public Sol(){var d=rla();N=(int)d[0];X=d[1];A=rla();}static String rs(){return Console.ReadLine();}static int ri(){return int.Parse(Console.ReadLine());}static long rl(){return long.Parse(Console.ReadLine());}static double rd(){return double.Parse(Console.ReadLine());}static String[] rsa(){return Console.ReadLine().Split(' ');}static int[] ria(){return Array.ConvertAll(Console.ReadLine().Split(' '),e=>int.Parse(e));}static long[] rla(){return Array.ConvertAll(Console.ReadLine().Split(' '),e=>long.Parse(e));}static double[] rda(){return Array.ConvertAll(Console.ReadLine().Split(' '),e=>double.Parse(e));}}