CodeForces-Duff and Weight Lifting-[I/O加速]

CodeForces - Duff and Weight Lifting - #326 (Div. 1)
c++iostream I/O最適化
http://codeforces.com/contest...
いくつかの数字がありますが、いずれも2 n です.毎回いくつかの数字を取り出し、取り出す数字の和も2 n であることを保証する.少なくとも何回取りますか.
サンプル入力:5 1 1 2 3 3サンプル出力:2解:
私たちは最も簡単なサンプルから始めます.
サンプル入力は以下のように整理できます.xの後にこの数字の出現回数を示す.2^1 x 2 2^2 x 1 2^3 x 2
2つの同じべき乗の数が,ちょうど「等価変換」してより高い数になることを見出した.2^1 x 2 => 2^2 x 1
さらに既存の2^2を加えると、合計2つの2^2があります.そして、変換を続け、2^2 x 2 => 2^3 x 1
さらに既存の2つの2^3を加えると、3つの2^3があります.2^3 x 2+1
どちらかを取り出して[変換](Transform)を行い、最終的には2^3 x 1 2^4 x 1
そして,どのように操作しても2つの数をさらに組み合わせて変換することはできないことが分かった.今は2つの数があるので、答えは2です.
ここまですれば、その中の法則を見るのは難しくない. の下の「進位」です.

#include 
#include
#include
using namespace std;

int orz[1000000+10000];
int l[] ={1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576};
int search(int n){
    for(int i = 0;i<20;i++){
        if(l[i+1]>=n){
            return i;
        }
    }
    return -1;
}
int main(){
    std::ios::sync_with_stdio(false);  
    std::cin.tie(0);  
    int n,t;
    scanf("%d", &n);
    int step = 0;
    int max = 0;
    for(int i = 0;imax?t:max);
        orz[t]++;
    }
    for(int i = 0;i<=max;i++){
        if(orz[i] == 0) continue;
        int now_cnt = orz[i];
        int pow;
        while(now_cnt){
            if(now_cnt == 1) step++;
            now_cnt -= l[pow = log2(now_cnt)];
            orz[max=(i+pow>max?i+pow:max),i+pow]++;
        }
    }
    printf("%d
", step);
    return 0;
}

この2行は

std::ios::sync_with_stdio(false);  
std::cin.tie(0);  

いわゆるiostream最適化である.
1行目の原理は、iostreamとstdioのバインドを解除することである.
2行目の原理は、cinとcoutとの結合を解除することである.
詳しくはこの文章をご覧ください.
なぜ最適化するのですか?私が最初にこの問題を作ったのは51 nod(このサイトがこの問題の中国語の問題を提供している)の機械がとても辛いので、カードI/Oです.クレイジーTLE.
ACができる2つの方法を試してみました.1つ目は、c++の特性文をすべて削除し、printfとscanfを使用して、cで提出します.2つ目は、iostream最適化である.
余談:
時には、printfとscanfを自分で書き換えるほうが効率的です.getcharとputcharの関数が速いからです.
qscqeszeの島娘テンプレートから以下を抜粋します.

template inline T& RD(T &x){  
    //cin >> x;  
    //scanf("%d", &x);  
    char c; for (c = getchar(); c < '0'; c = getchar()); x = c - '0'; for (c = getchar(); '0' <= c && c <= '9'; c = getchar()) x = x * 10 + c - '0';  
    //char c; c = getchar(); x = c - '0'; for (c = getchar(); c >= '0'; c = getchar()) x = x * 10 + c - '0';  
    return x;  
}  
  
int ____Case; template inline void OT(const T &x){  
    //if (x == -1) printf("Case %d: NO
", ++____Case);  
    //else printf("Case %d: %d
", ++____Case, x);  
    //printf("%I64d
", x);  
    //printf("%.2lf
", x);  
    printf("%d
", x);  
    //cout << x << endl;  
}  

これは、scanfを書き換えたことに相当します.putcharでprintfを書き直すには......後で話しましょう.大量の出力に遭遇することは少ないからです.