Today I submit the solution for : Problem I — Gym 101061 using scanf/printf and it gives me TLE (Time limit exceeded on test 2). This is my solution:
#include <bits/stdc++.h>
using namespace std;
const int MAX = 1e5 + 10;
int T;
char s1[MAX], s2[MAX];
int c1[30], c2[30];
int main(){
scanf("%d", &T);
while(T--){
scanf("%s", s1);
scanf("%s", s2);
memset(c1, 0, sizeof(c1));
memset(c2, 0, sizeof(c2));
for(int i = 0; i < (int)strlen(s1); i++) c1[s1[i] - 'a']++;
for(int i = 0; i < (int)strlen(s2); i++) c2[s2[i] - 'a']++;
int res = 0;
for(int i = 0; i < 26; i++) res += abs(c1[i] - c2[i]);
printf("%d\n", res);
}
}
But when I change to cin/cout, I get AC in 15ms. This is the second solution:
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
int T;
string s1, s2;
int c1[30], c2[30];
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> T;
while(T--){
cin >> s1 >> s2;
memset(c1, 0, sizeof(c1));
memset(c2, 0, sizeof(c2));
for(int i = 0; i < (int)s1.size(); i++) c1[s1[i] - 'a']++;
for(int i = 0; i < (int)s2.size(); i++) c2[s2[i] - 'a']++;
int res = 0;
for(int i = 0; i < 26; i++) res += abs(c1[i] - c2[i]);
cout << res << endl;
}
}
I'm used to scanf/printf because I think it's fast but this time brings a huge doubt. Can anybody explain this for me? Is it because in cin/cout solution I use cin.tie(NULL)?
The huge difference doesn't come from I/O.
Actually, time complexity of
strlen()
is O(n) whilesize()
is O(1).Thus, time complexity of first one is O(n2) which will definitely get TLE.
Oh I see. Thank you. By the way, is there anything I can use instead of
strlen()
?You can store the sizes of s1 and s2 in separate variables before looping, then your solution still remains O(n).
Thanks