Hatena::Grouptopcoder

Wrong Answer -- japlj このページをアンテナに追加 RSSフィード

 | 

2011-01-17

PKU 3784 -- Running Median

| 18:47 | PKU 3784 -- Running Median - Wrong Answer -- japlj を含むブックマーク はてなブックマーク - PKU 3784 -- Running Median - Wrong Answer -- japlj PKU 3784 -- Running Median - Wrong Answer -- japlj のブックマークコメント

座標圧縮してsegtreeにぶちこむ。

O(PM log M) でも厳しいかなーと思ってたけど 16MS で終わったので P がとても小さい疑惑。ヘタすると O(PM2) が通るかも。


#include<cstdio>
#include<vector>
#include<algorithm>

using namespace std;

int main()
{
  int P;
  scanf("%d", &P);
  while(P--) {
    int n, m, o=0, num[(1<<15)+50] = {0};
    scanf("%d%d", &n, &m);
    printf("%d %d\n", n, (m+1)/2);
    vector<int> p(m), q;
    for(int i=0; i<m; ++i) scanf("%d", &p[i]);
    q = p;
    sort(q.begin(), q.end());
    q.erase(unique(q.begin(), q.end()), q.end());
    for(int i=0; i<m; ++i) {
      int x = lower_bound(q.begin(), q.end(), p[i])-q.begin();
      for(int j=(1<<14)+x; j>=1; j>>=1) num[j]++;
      if(i%2) continue;
      int y=1, k=i/2;
      while(true) {
	if(y >= 1<<14) {
	  printf("%d%c", q[y-(1<<14)], "\n "[!!(++o%10)]);
	  break;
	}
	if(num[2*y]<=k) k-=num[2*y], y=2*y+1; else y*=2;
      }
    }
    if(o%10) puts("");
  }
  return 0;
}

PKU 3783 -- Balls

| 18:20 | PKU 3783 -- Balls - Wrong Answer -- japlj を含むブックマーク はてなブックマーク - PKU 3783 -- Balls - Wrong Answer -- japlj PKU 3783 -- Balls - Wrong Answer -- japlj のブックマークコメント

DPするだけ。


#include<cstdio>
#include<algorithm>

using namespace std;

int dp[1001][51];

int main()
{
  int P;
  scanf("%d", &P);
  for(int i=1; i<=50; ++i)
    dp[1][i] = 1;
  for(int i=1; i<=1000; ++i)
    dp[i][1] = i;
  for(int i=2; i<=1000; ++i)
    for(int j=2, k; j<=50; ++j)
      for(dp[i][j]=i, k=1; k<=i; ++k)
	dp[i][j] = min(dp[i][j], max(dp[k-1][j-1], dp[i-k][j])+1);
  while(P--) {
    int n, b, m;
    scanf("%d%d%d", &n, &b, &m);
    printf("%d %d\n", n, dp[m][b]);
  }
  return 0;
}

PKU 3782 -- Equal Sum Partitions

| 16:53 | PKU 3782 -- Equal Sum Partitions - Wrong Answer -- japlj を含むブックマーク はてなブックマーク - PKU 3782 -- Equal Sum Partitions - Wrong Answer -- japlj PKU 3782 -- Equal Sum Partitions - Wrong Answer -- japlj のブックマークコメント

全部試す。枝刈りで間に合う。


#include<cstdio>

using namespace std;

int main()
{
  int P;
  scanf("%d", &P);
  while(P--) {
    int n, m, a[10000], s=0;
    scanf("%d%d", &n, &m);
    for(int i=0; i<m; ++i) scanf("%d", &a[i]), s+=a[i];
    for(int i=0, j, p=0; i<m; ++i) {
      p += a[i];
      if(s % p == 0) {
	int q = 0;
	for(j=i+1; j<m; ++j) {
	  if((q += a[j]) == p) q = 0;
	  else if(q > p) break;
	}
	if(j==m && q==0) {
	  printf("%d %d\n", n, p);
	  break;
	}
      }
    }
  }
  return 0;
}

PKU 3781 -- Nth Largest Value

| 16:49 | PKU 3781 -- Nth Largest Value - Wrong Answer -- japlj を含むブックマーク はてなブックマーク - PKU 3781 -- Nth Largest Value - Wrong Answer -- japlj PKU 3781 -- Nth Largest Value - Wrong Answer -- japlj のブックマークコメント

やるだけ。


#include<cstdio>
#include<algorithm>

using namespace std;

int main()
{
  int P;
  scanf("%d", &P);
  while(P--) {
    int a[11];
    for(int i=0; i<11; ++i) scanf("%d", &a[i]);
    sort(a+1, a+11);
    printf("%d %d\n", a[0], a[8]);
  }
  return 0;
}
 |