Show all threads Hide all threads Show all messages Hide all messages |
WA3 | pizdec | 1713. Key Substrings | 15 Aug 2018 14:22 | 1 |
WA3 pizdec 15 Aug 2018 14:22 I use suffix array but WA3. Give me some tests. #include <string> #include <iostream> using namespace std; int min(int x, int y) { return x < y ? x : y; } int max(int x, int y) { return x > y ? x : y; } int Min(int l, int r); const int nmax = 1005; const int maxlen = 1000 * 105; const int alphabet = 256; int n, m, sum; int p[maxlen], cnt[maxlen], c[maxlen]; int pn[maxlen], cn[maxlen], lcp[maxlen]; int who[maxlen], up[maxlen], down[maxlen], a[nmax], b[nmax]; int ans_len[nmax], ans_ind[nmax]; string s, str[nmax]; int main() { cin>>m; for(int i=0;i<m;i++) cin>>str[i], s+=str[i]; m++; str[m-1]="#"; s+=str[m-1];
n = s.length(); memset(cnt, 0, alphabet * sizeof(int)); for (int i = 0; i<n; ++i) ++cnt[s[i]]; for (int i = 1; i<alphabet; ++i) cnt[i] += cnt[i - 1]; for (int i = 0; i<n; ++i) p[--cnt[s[i]]] = i; c[p[0]] = 0; int classes = 1; for (int i = 1; i<n; ++i) { if (s[p[i]] != s[p[i - 1]]) ++classes; c[p[i]] = classes - 1; } for (int h = 0; (1 << h)<n; ++h) { for (int i = 0; i<n; ++i) { pn[i] = p[i] - (1 << h); if (pn[i] < 0) pn[i] += n; } memset(cnt, 0, classes * sizeof(int)); for (int i = 0; i<n; ++i) ++cnt[c[pn[i]]]; for (int i = 1; i<classes; ++i) cnt[i] += cnt[i - 1]; for (int i = n - 1; i >= 0; --i) p[--cnt[c[pn[i]]]] = pn[i]; cn[p[0]] = 0; classes = 1; for (int i = 1; i<n; ++i) { int mid1 = (p[i] + (1 << h)) % n, mid2 = (p[i - 1] + (1 << h)) % n; if (c[p[i]] != c[p[i - 1]] || c[mid1] != c[mid2]) ++classes; cn[p[i]] = classes - 1; } memcpy(c, cn, n * sizeof(int)); } n--, m--, s.erase(n, 1); for (int i = 0; i < n; i++) p[i] = p[i + 1]; sum = 0; for (int i = 0; i < m; i++) a[i]=sum, b[i]=sum+str[i].length()-1, sum += str[i].length();
for (int i = 0; i < n; i++) { int j = 0; while (!(a[j] <= p[i] && p[i] <= b[j])) j++; who[i] = j; }
for (int i = 0; i <= n - 2; i++) { lcp[i] = 0; int hr = max(p[i], p[i+1]); int gr = min(b[who[i]]-p[i]+1, b[who[i+1]]-p[i+1]+1); while (hr+lcp[i]<n && lcp[i]<gr && s[p[i] + lcp[i]] == s[p[i + 1] + lcp[i]]) lcp[i]++; } down[0] = -1; for (int i = 1; i < n; i++) down[i] = who[i - 1] == who[i]? down[i - 1] : i - 1;
up[n - 1] = -1; for (int i = n - 2; i >= 0; i--) up[i] = who[i + 1] == who[i] ? up[i + 1] : i + 1; for (int i = 0; i < m; i++) ans_len[i] = str[i].length(), ans_ind[i]=a[i]; for (int i = 0; i < n; i++) { int val1 = down[i] == -1 ? 0 : Min(down[i], i - 1); int val2 = up[i] == -1 ? 0 : Min(i, up[i]-1); int now_len = max(val1, val2) + 1; if (now_len<=b[who[i]]-p[i]+1 && ans_len[who[i]] > now_len) ans_len[who[i]] = now_len, ans_ind[who[i]] = p[i]; } for (int i = 0; i < m; i++) { for (int j = 0; j < ans_len[i]; j++) cout << s[ans_ind[i] + j]; if(i+1<m) cout << endl; } return 0; } int Min(int l, int r) { int res=maxlen+5; for(int i=l;i<=r;i++) res=min(res, lcp[i]); return res; } Edited by author 16.08.2018 00:42 |
some tests | Gleb | 2103. Corporate Mail | 15 Aug 2018 12:25 | 1 |
This tests helped me to find bugs with wa5 and wa84 5 8 answer: 1 3 5 4 8 ----- 5 18 answer: 1 3 5 6 18 ----- 7 25 answer: 2 3 7 5 25 |
Who can tell me the reason? WA on test 8 | felomid | 1012. K-based Numbers. Version 2 | 15 Aug 2018 08:22 | 1 |
this is my code G++ #include<bits/stdc++.h> using namespace std; int n,k; void pl(int a[],int b[],int c[]) { for(int i=1;i<=210;i++) { c[i]+=a[i]+b[i]; c[i+1]+=c[i]/10; c[i]%=10; } }
void cheng(int a[],int x) { for(int i=1;i<=210;i++) { a[i]*=x; a[i]+=(a[i-1]/10); a[i-1]%=10; } } int f[2000][222]; int main() { scanf("%d%d",&n,&k); f[0][0]=0; f[1][0]=1; f[1][1]=k-1; for(int i=2;i<=n;i++) { pl(f[i-2],f[i-1],f[i]); cheng(f[i],k-1); } for(int i=1;i<=210;i++) { f[n][i]+=f[n-1][i]; f[n][i+1]+=f[n][i]/10; f[n][i]%=10; } int h=221; while(!f[n][h]) h--; for(int i=h;i>=1;i--) printf("%d",f[n][i]); return 0; } |
What's the test 4?? | zylm | 1027. D++ Again | 14 Aug 2018 17:20 | 2 |
I use "string ch" AC,but " char ch[maxn]" WA4,I don't know why ..... You may be forgetting that C strings contain ONE more character that is called terminal character (or whatever). So it must be 10001. And it works! for me |
2 Admins: I probably found bad test for my AC solution | Khranovsky`~ | 1027. D++ Again | 14 Aug 2018 17:11 | 2 |
Test: ((**)*) My answer is YES, but if we delete comment (**) it will remain only (*) and it must be arithmetic expr, but it's not cuz arithmetic expressions can't start with (*, so the right answer is NO, am I wrong? You are wrong. There are no rules for comments if there are no comments. lol |
sort & lower_bound functions from library is enough | imaginary friend | 1613. For Fans of Statistics | 14 Aug 2018 03:14 | 1 |
|
To admins: the statement corrections | Fyodor Menshikov | 1111. Squares | 13 Aug 2018 23:16 | 1 |
Could you specify in the problem statement that the coordinates of the point in the last line are integer? Also, could you specify the kind of precision near 10^{-14}? Is it absolute or relative? |
Problem 1075 "Thread in a Space" has been rejudged | Vladimir Yakovlev (USU) | 1075. Thread in a Space | 12 Aug 2018 19:36 | 2 |
New tests have been added to the problem which exploit a common mistake when using acos function. Hint: try to calculate acos(sqrt(3.0) * sqrt(3.0) - 4.0) in your programming language. 649 authors (60%) with accepted solutions have been challenged. Why point out the weak place!? I've found mistake without this hint, it wasnt that hard. |
about wa2 | Gleb | 1602. Elevator | 11 Aug 2018 18:08 | 1 |
in this test Petr should go to 1 floor |
8 test | Artem | 1269. Obscene Words Filter | 11 Aug 2018 00:25 | 1 |
8 test Artem 11 Aug 2018 00:25 |
What is Test case #5 | Krishnan | 1104. Don’t Ask Woman about Her Age | 10 Aug 2018 17:39 | 4 |
What is Test case #5 for question 1104 Output is "No solution.". (!) BE CAREFUL NOT "No solution" but "No solution." Output is "No solution.". (!) BE CAREFUL NOT "No solution" but "No solution." Thanks... |
How to fix the Compilation Error ? | Min Aung Dain | 1000. A+B Problem | 10 Aug 2018 16:29 | 3 |
I wrote the code in python as below x = input().split(' ') a = int(x[0]) b = int(x[1]) sum = a + b print(sum) But it shows compilation error and I don't know what causes it and how to fix it. mb you were wrong when you selected the language? yeah, check, u selected FreePascal 2.6 |
Bigger=MLE Smaller=RE???? | ZhaoJInsong | 1012. K-based Numbers. Version 2 | 10 Aug 2018 09:40 | 2 |
#include <iostream> #include <fstream> #include <cstdio> #include <cassert> #include <complex> #include <cmath> #include <algorithm> #include <vector> #include <string> #include <cstdlib> #include <cstring> #include <iomanip> #include <numeric> #include <sstream> #include <ctime> #include <cctype> #include <set> #include <map> #include <queue> #include <bitset> #include <deque> #include <stack> #include <memory.h> using namespace std; typedef long long ll; #define mp make_pair const int MAXN =1500;
struct bign { int len, s[MAXN]; bign () { memset(s, 0, sizeof(s)); len = 1; } bign (int num) { *this = num; } bign (const char *num) { *this = num; } bign operator = (const int num) { char s[MAXN]; sprintf(s, "%d", num); *this = s; return *this; } bign operator = (const char *num) { for(int i = 0; num[i] == '0'; num++) ; //ȥǰµ¼0 len = strlen(num); for(int i = 0; i < len; i++) s[i] = num[len-i-1] - '0'; return *this; } bign operator + (const bign &b) const //+ { bign c; c.len = 0; for(int i = 0, g = 0; g || i < max(len, b.len); i++) { int x = g; if(i < len) x += s[i]; if(i < b.len) x += b.s[i]; c.s[c.len++] = x % 10; g = x / 10; } return c; } bign operator += (const bign &b) { *this = *this + b; return *this; } void clean() { while(len > 1 && !s[len-1]) len--; } bign operator * (const bign &b) //* { bign c; c.len = len + b.len; for(int i = 0; i < len; i++) { for(int j = 0; j < b.len; j++) { c.s[i+j] += s[i] * b.s[j]; } } for(int i = 0; i < c.len; i++) { c.s[i+1] += c.s[i]/10; c.s[i] %= 10; } c.clean(); return c; } bign operator *= (const bign &b) { *this = *this * b; return *this; } bign operator - (const bign &b) { bign c; c.len = 0; for(int i = 0, g = 0; i < len; i++) { int x = s[i] - g; if(i < b.len) x -= b.s[i]; if(x >= 0) g = 0; else { g = 1; x += 10; } c.s[c.len++] = x; } c.clean(); return c; } bign operator -= (const bign &b) { *this = *this - b; return *this; } bign operator / (const bign &b) { bign c, f = 0; for(int i = len-1; i >= 0; i--) { f = f*10; f.s[0] = s[i]; while(f >= b) { f -= b; c.s[i]++; } } c.len = len; c.clean(); return c; } bign operator /= (const bign &b) { *this = *this / b; return *this; } bign operator % (const bign &b) { bign r = *this / b; r = *this - r*b; return r; } bign operator %= (const bign &b) { *this = *this % b; return *this; } bool operator < (const bign &b) { if(len != b.len) return len < b.len; for(int i = len-1; i >= 0; i--) { if(s[i] != b.s[i]) return s[i] < b.s[i]; } return false; } bool operator > (const bign &b) { if(len != b.len) return len > b.len; for(int i = len-1; i >= 0; i--) { if(s[i] != b.s[i]) return s[i] > b.s[i]; } return false; } bool operator == (const bign &b) { return !(*this > b) && !(*this < b); } bool operator != (const bign &b) { return !(*this == b); } bool operator <= (const bign &b) { return *this < b || *this == b; } bool operator >= (const bign &b) { return *this > b || *this == b; } string str() const { string res = ""; for(int i = 0; i < len; i++) res = char(s[i]+'0') + res; return res; } };
istream& operator >> (istream &in, bign &x) { string s; in >> s; x = s.c_str(); return in; }
ostream& operator << (ostream &out, const bign &x) { out << x.str(); return out; } bign dp[1800][2]; bign k; int n; int main() { cin>>n>>k; dp[0][0]=k-1; dp[0][1]=0; for(int i=1;i<n;i++){ dp[i][0]=(k-1)*(dp[i-1][0]+dp[i-1][1]); dp[i][1]=dp[i-1][0]; } cout<<dp[n-1][0]+dp[n-1][1]; return 0; } my bigint struct hope will help const int T=400, MOD=10000000; struct bigInt { int a[T], n; bigInt(){}; bigInt(int x) { memset(a, 0, sizeof a); n = 1, a[0] = x; } void init(int x) { n = 1; a[0] = x; } bool operator < (const bigInt &x) { if (n < x.n) return 1; else if (n > x.n) return 0; for (int i=n-1; i>=0; i--) if (a[i] < x.a[i]) return 1; else if (a[i] > x.a[i]) return 0; return 0; } bigInt operator * (const bigInt &x) { bigInt t(0); t.n = x.n + n - 1; for (int i=0; i<n; i++) for (int j=0; j<x.n; j++) t.a[i+j]+=a[i]*x.a[j]; for (int i=0; i<t.n; i++) { t.a[i+1]+=t.a[i]/MOD; t.a[i]%=MOD; } if (t.a[t.n]) t.n++; return t; } bigInt operator + (const bigInt &x) { bigInt t(0); t.n = max(x.n, n); for (int i=0; i<t.n; i++) { t.a[i] = t.a[i] + x.a[i] + a[i]; t.a[i+1]+=t.a[i]/MOD; t.a[i]%=MOD; } if (t.a[t.n]) t.n++; return t; } void print() { printf("%d",a[n-1]); for (int i=n-2; i>=0; i--) printf("%07d",a[i]); puts(""); } }; Ps:this will only work with the + operator. To get AC, I changed the base from 10000 to 10000000, so the * operator won't work. |
WA#37 | gautamvs | 1891. Language Ocean | 9 Aug 2018 20:10 | 2 |
WA#37 gautamvs 9 Dec 2012 18:41 Please, somebody provide with test case ... Check for "Invalid initialization" case. Edited by author 09.08.2018 20:10 |
C: Why doesn't the recursion stop? | y87cgp | 1001. Reverse Root | 9 Aug 2018 18:16 | 1 |
#include <stdio.h> #include <math.h> void recur(void); int main() {
recur(); return 0; } void recur() { long int num; scanf("%ld", &num); if (num != EOF) recur(); printf("%.5f\n", sqrt(num)); } Edited by author 09.08.2018 18:20 |
little asvice (no spoilers) | bstu_student | 1654. Cipher Message | 9 Aug 2018 09:09 | 1 |
char[200001] gives perfect time if you will check repeats while string is inputting |
use printf() instead of cout and string instead of char if you use c++ stl | Haloom | 1654. Cipher Message | 9 Aug 2018 09:08 | 2 |
i used deque. cout got me TLE.using printf save me. if(st.front()!=s[i]) { st.emplace_front(s[i]); } else st.pop_front();
for(it=st.end()-1; it>=st.begin(); it--) { printf("%c",*it); } i say more - it's better don't use stl-containers if it's possible. char[200001] gives perfect time |
Why my code doesn't work with c++ 'sort' ? But it works fine with stable_sort o_O | sirius_lyra | 1100. Final Standings | 9 Aug 2018 06:09 | 3 |
/* * @Author: eleven * @Date: 2017-05-21 02:50:38 * @Last Modified by: eleven * @Last Modified time: 2018-02-09 14:49:14 */ // Status : AC ( works with stable_sort ) // doesn't works with sort #include <bits/stdc++.h> using namespace std; #define SIZE 150005 struct team{ int id; int solved; }teams[SIZE]; bool foo(team lhs, team rhs){ return lhs.solved > rhs.solved; } void print(int n ){ for(int i= 0; i<n ; ++i){ cout<<teams[i].id<<" "<<teams[i].solved<<'\n'; } } int main(){ //freopen("in","r",stdin); //freopen("out","w",stdout); int n ; cin>>n; for(int i = 0; i<n ; ++i){ cin>>teams[i].id>>teams[i].solved; } stable_sort(teams,teams+n ,foo); print(n); return 0; } I don't know why, but i have tha same problem. WA with sort, AC with stable_sort *go to read faq's* #define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <algorithm> using namespace std; pair <int, int> a[150000]; int n; bool comp(pair <int, int> a, pair <int, int> b) { return a.first > b.first; } int main() { scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d%d", &a[i].second, &a[i].first); stable_sort(a, a + n, comp); //sort(a, a+n,comp); for (int i=0;i<n;i++) printf("%d %d\n", a[i].second, a[i].first); return 0; } OK, i've found yhe answere - stable_sort keeps the relative order berween equal elements... because this is stable sort)) |
C++ 11 STL AC | coldwind | 1545. Hieroglyphs | 8 Aug 2018 14:28 | 1 |
#include<iostream> #include<string> #include<map> #include<set> using namespace std; int main(){ map<char,set<string>> dic; string w; int n; cin>>n; while(--n>=0){ cin>>w; dic[w[0]].insert(w); } char c; cin>>c; for(auto s:dic[c]) cout<<s<<endl; } |
See If you are getting WA 7 | Ashish Nimbalkar | 1203. Scientific Conference | 7 Aug 2018 14:30 | 1 |
If you are using DP, make sure you are using multimap instead of map ( In c++ )
|