結果
問題 | 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));} }