On the first sight i thought i'd need O(3 ^ 16) but the problem is much easier. print "IMPOSSIBLE" instead of "Impossible" Thank you so much! I've made the stupid mistake too XD if your store data in array of pairs begin loop from zero i=0 not from 1! I had wa28, too my mistake was a incorrect comparison of strings for example s1="bb"; s2="bbbb"; f(s1,s2); // give true s1<s2 f(s2,s1); // give me too true, but this is mistake When I have corrected this i had ac sorry for my english)) Edited by author 11.10.2009 12:23 i get WA28,too. i try your way but it is useless. plz help me! Edited by author 05.01.2019 17:36 //#pragma GCC optimize("Ofast,no-stack-protector") //#pragma GCC target("avx") #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds; using namespace std;
#define re return #define pb push_back #define eb emplace_back #define all(x) (x).begin(), (x).end() #define fi first #define se second #define sqrt(x) sqrt(abs(x)) #define mp make_pair #define pi (3.14159265358979323846264338327950288419716939937510) #define fo(i, n) for(int i = 0; i < n; ++i) #define ro(i, n) for(int i = n - 1; i >= 0; --i) #define unique(v) v.resize(unique(all(v)) - v.begin())
template <class T> T abs (T x) { re x > 0 ? x : -x; } template <class T> T sqr (T x) { re x * x; } template <class T> T gcd (T a, T b) { re a ? gcd (b % a, a) : b; } template <class T> int sgn (T x) { re x > 0 ? 1 : (x < 0 ? -1 : 0); }
typedef vector<int> vi; typedef vector<vi> vvi; typedef pair<int, int> ii; typedef vector<ii> vii; typedef vector<string> vs; typedef double D; typedef long double ld; typedef long long ll; typedef pair<ll, ll> pll; typedef vector<ll> vll; typedef unsigned long long ull; typedef tree <pair<int, char>, null_type, less<pair<int, char>>, rb_tree_tag, tree_order_statistics_node_update> _tree; const int maxn = 20; int n; string s[20][3]; int p[maxn]; vector <string> ans; bool was[maxn][3]; bool f (int pos, int last = -1) { if (pos == n) re true; if (pos && was[pos][last]) re false; if (pos) was[pos][last] = true; if (pos) { fo(i, 3) { if (s[p[pos - 1]][last] < s[p[pos]][i] && f(pos + 1, i)) { ans.pb(s[p[pos]][i]); re true; } } } else { fo(i, 3) { if (f(pos + 1, i)) { ans.pb(s[p[pos]][i]); re true; } } } re false; } int main() { cin >> n; fo(i, n) fo(j, 3) cin >> s[i][j]; fo(i, n) cin >> p[i], p[i]--; if (f(0)) { reverse(all(ans)); for (string &s : ans) cout << s << '\n'; } else cout << "IMPOSSIBLE\n"; re 0; } What is test #25? me help test --------------------------------------------------- 16 cipher grille kamkohob names grillee pcodes newtests rejudge timus size volume summit watchmen braineater twosides solution random yesorno keywords subversion commands bosses shooting shaitan game strategy playgame mnemonic palindromes bestname eligibility rectangle rules txxxxxxx txxxyzasd txxxxxas volvo vlot volt vvv vvilia vvobla what is it zina whashing potatoes 2 1 7 10 9 6 11 3 8 4 5 12 13 14 15 16 ------------------------------------------------ answer is ------------------------------------------------ grillee kamkohob keywords mnemonic playgame random rectangle rejudge shaitan size twosides txxxxxas vlot vvilia what zina For your test,i got the same answer ,but my code wa#20 I've had this problem too. THen i found my mistake. My function that compared two strings and returned the lower one: f f("aa","aaaa")="aa"; f("aaaaa","aa")="aaaaa"; - this was a mistake. It should have returned "aa" sorry for my English Уважаемые администраторы сайта! Подскажите, пожалуйста, что Вы собираетесь делать с посылками, которые получали AC на компиляторе Intel C++ 7, и получают Time Limit на компиляторах G++ 4.7.2 и Visual C++ 2010? У меня, например, около 4-5 таких задач было, пришлось все их перерешивать по-другому. Ведь теперь нет возможности отправить задачу на старом компиляторе. Извиняйте, но тогда нужно перетестировать посылки под Intel C++ 7 на новых компиляторах, а то результаты и рейтинг получаются НЕЧЕСТНЫМИ !!! Ведь не все перерешивают уже "сданные" задачи. In JAVA version of the tests, in test 3, N<3, be careful when declaring array sizes. In C# version of the tests there is no such test. Who can give me some tests? #include<iostream> #include<string> #include<stdio.h> #include<stdlib.h> using namespace std; int main() { int b[26],n,i,j;bool t=true; string a[26][3],str,s[26]; cin>>n; for(i=0;i<n;i++) { cin>>a[i][0]; cin>>a[i][1]; cin>>a[i][2]; if(a[i][1]>a[i][2]) { str=a[i][1]; a[i][1]=a[i][2]; a[i][2]=str; }
if(a[i][0]>a[i][1]) { str=a[i][0]; a[i][0]=a[i][1]; a[i][1]=str; }
} /* for(i=0;i<n;i++) {for(j=0;j<3;j++) cout<<a[i][j]<<" "; cout<<endl; } */ for(i=0;i<n;i++) { cin>>b[i]; if(i==0) s[i]=a[b[i]-1][0]; else{j=0; while(a[b[i]-1][j]<=s[i-1]&&j<3) {
j++;} if(a[b[i]-1][j]>s[b[i]-1]) s[i]=a[b[i]-1][j]; else t=false; }
} if(t) for(i=0;i<n;i++) cout<<s[i]<<endl; else cout<<"IMPOSSIBLE";
system("pause"); } Instead of shaitan volume watchmen Shooting Size Watchmen (!) "If there are several possible answers, output any of them" Both of them are correct. I sort all variants for each problem in lexicographic order. First I output first variant for first problem. Next I compare last outputted word and first variant fo next problem, if it is not satisfies I compare last output and second word etc. If all variants are incorrect I print "IMPOSSIBLE". Last I print words in founded order. Where is my mistake? Sorry for my English. From the 3 names you should choose the "SMALLEST" one that is bigger than "the last outputted word". And you should not print the words one by one, because at some point you could find out that it's "IMPOSSIBLE". Store your answers in array or something like that. String comparison: s1="aa"; s2="aaa"; s1<s2==true; s2>s1==false; omg s2>s1!=s1<s2? Don't know about you, but for me it's like this :) "aa" > "aaa" FALSE "aaa" < "aa" FALSE "aa" < "aaa" TRUE "aaa" > "aa" TRUE Standart C++ operation. Maybe you're using other language and you have this problem? Edited by author 09.08.2011 00:39 Could you say what's in test #7? It files but can't see any errors in my solution :( My program passed all tests from forum. I sorted with c++ string comparision operator '<', and wrote my own function. But, anyway WA #25? Why??? What exactly you was sorted? Solution for this problem need not any kind of sort. What exactly you was sorted? Solution for this problem need not any kind of sort. I've sorted possible names in every problem, than sorted all problems by their order. please, help me... my code: #include <iostream> using namespace std; int main() { int n,m[16],k; char c[48][20],v[16][20],ch[3][20]; cin>>n; for(int i=0;i<n*3;i++) cin>>c[i]; for(int i=0;i<n;i++) { cin>>k; m[i]=k; } k=(m[0]-1)*3; if((strcmp(c[k],c[k+1])<=0)&&(strcmp(c[k],c[k+2])<=0)){strcpy(v[0],c[k]);} if((strcmp(c[k+1],c[k])<=0)&&(strcmp(c[k+1],c[k+2])<=0)){strcpy(v[0],c[k+1]);} if((strcmp(c[k+1],c[k])<=0)&&(strcmp(c[k+1],c[k+2])<=0)){strcpy(v[0],c[k+1]);} for(int i=1;i<n;i++) { k=(m[i]-1)*3; if((strcmp(c[k],c[k+1])<=0)&&(strcmp(c[k],c[k+2])<=0)) { strcpy(ch[0],c[k]); if(strcmp(c[k+1],c[k+2])<=0) { strcpy(ch[1],c[k+1]); strcpy(ch[2],c[k+2]); } else { strcpy(ch[2],c[k+1]); strcpy(ch[1],c[k+2]); } }
if((strcmp(c[k+1],c[k])<=0)&&(strcmp(c[k+1],c[k+2])<=0)) { strcpy(ch[0],c[k+1]); if(strcmp(c[k],c[k+2])<=0) { strcpy(ch[1],c[k]); strcpy(ch[2],c[k+2]); } else { strcpy(ch[2],c[k]); strcpy(ch[1],c[k+2]); } }
if((strcmp(c[k+2],c[k])<=0)&&(strcmp(c[k+2],c[k+1])<=0)) { strcpy(ch[0],c[k+2]); if(strcmp(c[k],c[k+1])<=0) { strcpy(ch[1],c[k]); strcpy(ch[2],c[k+1]); } else { strcpy(ch[2],c[k]); strcpy(ch[1],c[k+1]); } }
if(strcmp(v[i-1],ch[0])<=0) { strcpy(v[i],ch[0]); } else { if(strcmp(v[i-1],ch[1])<=0) { strcpy(v[i],ch[1]); } else { if(strcmp(v[i-1],ch[2])<=0) { strcpy(v[i],ch[2]); } else { cout<<"IMPOSSIBLE"; return 0; } } } } for(int i=0;i<n;i++) { cout<<v[i]<<endl; } return 0; } why my answer of the test#1 is incorrect? codenames grille keywords mnemonic playgame random rectangle rejudge shaitan size twosides its correct my program give this answer but i have wa28 and i don't understand why( try this 3 bbb bb b bbb bb b bbb bb b 1 2 3 output b bb bbb first,i get WA28, i get AC28,but WA1,now Edited by author 11.03.2010 13:31 @kecin, I think, that's incorrect test, because "All codenames are different", but my program output: b bb bbb On sample test my prog. works right too, but WA1 :( Edited by author 02.04.2010 19:55 I had WA 1 too, but now I have AC. This test helped me: 2 cipher grille kamkohob ciphez grillz kamkohoz 2 1 Possible answers: ciphez grille or ciphez kamkohob or grillz kamkohob my answer : codenames grille keywords mnemonic playgame random rectangle rejudge shaitan size twosides the first test is correct;) The first test in description does be correct. If you think that it isn't so, perhaps you hasn't understood the problem in the right way. First I was mistaken too. In the last line numbers mean the following: number 2: on the first place there should be the task number 2 (names, codenames, codes) number 1: on the second place there should be the task number 1 (cipher, grille, kamkohob) number 7: on the third (!!!) place there should be the task number 7 (keywords, subversion, commands) number 10: on the 4th (!!!) place there should be the task number 10 (mnemonic, palindromes, bestname) and so on. |
|