#25358: 請問這題會卡 C++ I/O 或字串處理時間嗎？
allllllan123456
(God of Computer Science)
學校
:
國立臺灣大學
編號 : 13732
來源 : [140.109.20.138]
最後登入時間 ：
2021-07-08 17:41:52
我有先試著把字串切成每 6 個 digit 一份存進一個 int 裡面，想說這樣可能比較省空間也比較快，還是這個操作本身就會 TLE 了？
如果直接拿字元下去運算會比較快嗎？懇請大大們指點...
#25363: Re:請問這題會卡 C++ I/O 或字串處理時間嗎？
allllllan123456
(God of Computer Science)
學校
:
國立臺灣大學
編號 : 13732
來源 : [140.109.20.138]
最後登入時間 ：
2021-07-08 17:41:52
我有先試著把字串切成每 6 個 digit 一份存進一個 int 裡面，想說這樣可能比較省空間也比較快，還是這個操作本身就會 TLE 了？
如果直接拿字元下去運算會比較快嗎？懇請大大們指點...
需要有人幫看 TLE 的程式碼... 感謝各位
#include <stdio.h>
int MOD = 10, len[2];
char div[2][300005], ch;
int main() {
int T; scanf("%d ", &T);
while (T--) { int cnt = 0;
len[0] = len[1] = 0;
while ((ch=getchar()) && ch!='\n' && ch!=EOF) {
if (ch == ' ') { cnt++; continue; }
div[cnt][len[cnt]] = ch - '0'; len[cnt]++;
}
int div1v = div[1][0] + (len[1]>=2) * (div[1][0]*(MOD-1) + div[1][1]);
char first = 1; // bool
if (len[0] < len[1]) putchar('0');
else
for (int lb=len[1]-1; lb<len[0]; lb++) {
int ub = lb+1-len[1];
if (ub>=1 && div[0][ub-1]) div[0][ub] += div[0][ub-1] * MOD;
int div0v = div[0][ub] + (len[1]>1) * (div[0][ub]*(MOD-1) + (ub+1<len[0])*div[0][ub+1]);
int q = div0v / div1v; q -= (q >= MOD);
for (int i=0; i<len[1]; i++) {
div[0][lb-i] -= div[1][len[1]-1-i] * q;
if (div[0][lb-i]<0 && lb-i-1>=ub) {
int t = (div[0][lb-i] % MOD + MOD) % MOD;
div[0][lb-i-1] -= (t - div[0][lb-i]) / MOD;
div[0][lb-i] = t;
}
}
if (div[0][ub]<0) { q--;
for (int i=0; i<len[1]; i++) {
div[0][lb-i] += div[1][len[1]-1-i];
if (div[0][lb-i] >= MOD) {
div[0][lb-i] -= MOD;
div[0][lb-i-1]++;
}
}
}
if (first && (q || lb==len[0]-1)) {
putchar(q + '0');
first = 0;
} else if (!(first && !q))
putchar(q + '0');
}
putchar('\n');
}
return 0;
}
#25364: Re:請問這題會卡 C++ I/O 或字串處理時間嗎？
getchar 和 putchar 改成 getchar_unlocked 和 putchar_unlocked 應該會比較快 但不知道會不會本身演算法就TLE
ZeroJudge Forum