fork download
copy 
  1. #include<bits/stdc++.h>
  2. #include "testlib.h"
  3.  
  4. using namespace std;
  5.  
  6. int palindrome(string s)
  7. {
  8.     for (int i = 0; i < s.size(); i++)
  9.     {
  10.         if (s[i] != s[(int) s.size() - i - 1])
  11.             return false;
  12.     }
  13.     return true;
  14. }
  15.  
  16. int canDoWithSingleDelete(int position, string s)
  17. {
  18.     //return false;
  19.     string t = "";
  20.     for (int i = 0; i < s.size(); i++)
  21.         if (i == position)
  22.             continue;
  23.         else
  24.             t += s[i];
  25.     return palindrome(t);
  26. }
  27.  
  28. int valid(int center, string s)
  29. {
  30.     // case when we need to delete the center itself.
  31.     if (canDoWithSingleDelete(center, s))
  32.         return true;
  33.     if (canDoWithSingleDelete(0, s))
  34.         return true;
  35.     if (canDoWithSingleDelete((int) s.size() - 1, s))
  36.         return true;
  37.     for (int diff1 = 0; diff1 <= 1; diff1++)
  38.     for (int diff2 = 0; diff2 <= 1; diff2++)
  39.     {
  40.         int lptr = center - diff1;
  41.         int rptr = center + diff2;
  42.  
  43.         //cout << lptr << " " << rptr << endl;
  44.  
  45.         int lStart = lptr;
  46.         int rStart = rptr;
  47.  
  48.         while (lptr >= 0 && rptr < s.size())
  49.         {
  50.             if (s[lptr] != s[rptr])
  51.             {
  52.                 if (canDoWithSingleDelete(lptr, s)) return true;
  53.                 if (canDoWithSingleDelete(rptr, s)) return true;
  54.                 break;
  55.             }
  56.             lptr--;
  57.             rptr++;
  58.         }
  59.     }
  60.     return false;
  61. }
  62.  
  63. int smartSolve(string s)
  64. {
  65.     vector<int> centerCandidate;
  66.     for (int i = -2; i <= 2; i++)
  67.     {
  68.         int idx = s.size() / 2 + i;
  69.         if (idx >= 0 && idx < s.size())
  70.             centerCandidate.push_back(idx);
  71.     }
  72.     int ok = false;
  73.     for (int ct = 0; ct < centerCandidate.size(); ct++)
  74.     {
  75.         int center = centerCandidate[ct];
  76.         if (valid(center, s))
  77.         {
  78.             ok = true;
  79.             break;
  80.         }
  81.     }
  82.     return ok;
  83. }
  84.  
  85.  
  86.  
  87. int bruteSolve(string s)
  88. {
  89.     for (int i = 0; i < s.size(); i++)
  90.     {
  91.         string t = "";
  92.         for (int j = 0; j < s.size(); j++)
  93.         {
  94.             if (i == j) continue;
  95.             t += s[j];
  96.         }
  97.         if (palindrome(t))
  98.             return true;
  99.     }
  100.     return false;
  101. }
  102.  
  103. #define BRUTE
  104.  
  105. vector<string> testStrings;
  106.  
  107. void rec(int id, string s, int alphaSize, int len)
  108. {
  109.     if (id == len)
  110.     {
  111.         testStrings.push_back(s);
  112.     }
  113.     else
  114.     {
  115.         for (char ch = 'a'; ch <= 'a' + alphaSize; ch++)
  116.         {
  117.             string t = s;
  118.             t += ch;
  119.             rec(id + 1, t, alphaSize, len);
  120.         }
  121.     }
  122. }
  123.  
  124.  
  125. void check(string s)
  126. {
  127.     int ok1 = smartSolve(s);
  128.     int ok2 = bruteSolve(s);
  129.     if (ok1 != ok2)
  130.     {
  131.         cout << s << endl;
  132.         cout << ok1 << " " << ok2 << endl;
  133.         assert(ok1 == ok2);
  134.     }
  135. }
  136.  
  137. #define TEST_GEN
  138. //#define TEST2
  139.  
  140. void print(char file[], vector<string> a)
  141. {
  142.     ofstream out;
  143.     out.open(file);
  144.     out << a.size() << endl;
  145.     cout << a.size() << endl;
  146.     for (int i = 0; i < a.size(); i++)
  147.         out << a[i] << endl;
  148.     out.close();
  149. }
  150.  
  151. void gen(char file[])
  152. {
  153.     int totalLen = 0;
  154.     vector<string> strs;
  155.     for (int len = 2; len <= 30; len++)
  156.     {
  157.         for (int mask = 0; mask < (1 << len); mask++)
  158.         {
  159.             string s = "";
  160.             for (int i = 0; i < len; i++)
  161.                 if (mask & (1 << i))
  162.                     s += "a";
  163.                 else s += "b";
  164.             if (totalLen + s.size() <= 1000000)
  165.             {
  166.                 totalLen += s.size();
  167.                 strs.push_back(s);
  168.             }
  169.             else goto done;
  170.         }
  171.     }
  172.     done:
  173.         print(file, strs);
  174. }
  175.  
  176. void gen1(char file[])
  177. {
  178.     int totalLen = 0;
  179.     vector<string> strs;
  180.     for (int len = 2; len < 10; len++)
  181.     {
  182.         testStrings.clear();
  183.         rec(0, "", 3, len);
  184.         for (int i = 0; i < testStrings.size(); i++)
  185.         {
  186.             string s = testStrings[i];
  187.             if (totalLen + s.size() <= 1000000)
  188.             {
  189.                 totalLen += s.size();
  190.                 strs.push_back(s);
  191.             }
  192.             else goto done;
  193.         }
  194.     }
  195.     done:
  196.         print(file, strs);
  197. }
  198.  
  199. void gen2(char file[])
  200. {
  201.     int totalLen = 0;
  202.     vector<string> strs;
  203.     for (int len = 2; len < 10; len++)
  204.     {
  205.         testStrings.clear();
  206.         rec(0, "", len, len);
  207.         for (int i = 0; i < testStrings.size(); i++)
  208.         {
  209.             string s = testStrings[i];
  210.             if (totalLen + s.size() <= 1000000)
  211.             {
  212.                 totalLen += s.size();
  213.                 strs.push_back(s);
  214.             }
  215.             else goto done;
  216.         }
  217.     }
  218.     done:
  219.         print(file, strs);
  220. }
  221.  
  222. string createRandomPalin(int len)
  223. {
  224.     string s = "";
  225.     for (int i = 0; i < len / 2; i++)
  226.         s += (char) ('a' + rnd.next(0, 25));
  227.     string t = s;
  228.     reverse(t.begin(), t.end());
  229.     if (len % 2 == 0)
  230.         return s + t;
  231.     else
  232.     {
  233.         string ans = s;
  234.         ans += (char) ('a' + rnd.next(0, 25));
  235.         ans += t;
  236.         return ans;
  237.     }
  238. }
  239.  
  240. string change(string s, int place)
  241. {
  242.     string t = "";
  243.     for (int i = 0; i < place; i++)
  244.         t += s[i];
  245.     t += (char) ('a' + rnd.next(0, 25));
  246.     for (int i = place; i < s.size(); i++)
  247.         t += s[i];
  248.     return t;
  249. }
  250.  
  251. void gen3(char file[])
  252. {
  253.     int totalLen = 0;
  254.     vector<string> strs;
  255.     for (int tc = 0; tc < 10000; tc++)
  256.     {
  257.         int len = rnd.next(2, 1000);
  258.         string s = createRandomPalin(len);
  259.         int place = rnd.next(0, len - 1);
  260.         s = change(s, place);
  261.         if (totalLen + s.size() <= 1000000)
  262.         {
  263.             if (rnd.next(1, 2) == 2)
  264.             {
  265.                 int place = rnd.next(0, (int)s.size() - 1);
  266.                 s[place] = (char) ('a' + rnd.next(0, 25));
  267.             }
  268.             totalLen += s.size();
  269.             strs.push_back(s);
  270.         }
  271.         else goto done;
  272.     }
  273.     done:
  274.         print(file, strs);
  275. }
  276.  
  277. void gen4(char file[])
  278. {
  279.     int totalLen = 0;
  280.     vector<string> strs;
  281.     for (int tc = 0; tc < 10; tc++)
  282.     {
  283.         int len = 99999;
  284.         string s = createRandomPalin(len);
  285.         int place = rnd.next(0, len - 1);
  286.         s = change(s, place);
  287.         if (totalLen + s.size() <= 1000000)
  288.         {
  289.             if (rnd.next(1, 2) == 2)
  290.             {
  291.                 int place = rnd.next(0, (int)s.size() - 1);
  292.                 s[place] = (char) ('a' + rnd.next(0, 25));
  293.             }
  294.             totalLen += s.size();
  295.             strs.push_back(s);
  296.         }
  297.         else goto done;
  298.     }
  299.     done:
  300.         print(file, strs);
  301. }
  302.  
  303. void gen5(char file[])
  304. {
  305.     int totalLen = 0;
  306.     vector<string> strs;
  307.     for (int tc = 0; tc < 10; tc++)
  308.     {
  309.         int len = 99999;
  310.         string s = createRandomPalin(len);
  311.         int place = rnd.next(0, len - 1);
  312.         s = change(s, place);
  313.         if (totalLen + s.size() <= 1000000)
  314.         {
  315.             if (rnd.next(1, 2) == 2)
  316.             {
  317.                 for (int ct = 0; ct < rnd.next(1, 10); ct++)
  318.                 {
  319.                     int place = rnd.next(0, (int)s.size() - 1);
  320.                     s[place] = (char) ('a' + rnd.next(0, 25));
  321.                 }
  322.             }
  323.             totalLen += s.size();
  324.             strs.push_back(s);
  325.         }
  326.         else goto done;
  327.     }
  328.     done:
  329.         print(file, strs);
  330. }
  331.  
  332. int main(int argc, char *argv[])
  333. {
  334.      registerGen(argc, argv);
  335.  
  336. #ifdef BRUTE
  337.  
  338. #ifdef TEST1
  339.     for (int len = 2; len <= 15; len++)
  340.     {
  341.         for (int mask = 0; mask < (1 << len); mask++)
  342.         {
  343.             string s = "";
  344.             for (int i = 0; i < len; i++)
  345.                 if (mask & (1 << i))
  346.                     s += "a";
  347.                 else s += "b";
  348.             int ok1 = smartSolve(s);
  349.             int ok2 = bruteSolve(s);
  350.             if (ok1 != ok2)
  351.             {
  352.                 cout << s << endl;
  353.                 cout << ok1 << " " << ok2 << endl;
  354.                 assert(ok1 == ok2);
  355.             }
  356.         }
  357.     }
  358. #endif // TEST1
  359.  
  360. #ifdef TEST2
  361.     int total = 0;
  362.     for (int len = 2; len < 10; len++)
  363.     {
  364.         testStrings.clear();
  365.         rec(0, "", len);
  366.         for (int i = 0; i < testStrings.size(); i++)
  367.         {
  368.             //cout << testStrings[i] << endl;
  369.             check(testStrings[i]);
  370.             total += testStrings[i].size();
  371.         }
  372.     }
  373.     cout << total << endl;
  374. #endif // TEST1
  375.  
  376. #else
  377.     int T;
  378.     cin >> T;
  379.     assert(T >= 1 && T <= 1000000);
  380.     while (T--)
  381.     {
  382.         string s;
  383.         cin >> s;
  384.         assert(s.size() >= 2 && s.size() <= 100000);
  385.         if (smartSolve(s)) cout << "YES" << endl;
  386.         else cout << "NO" << endl;
  387.     }
  388. #endif // BRUTE
  389.  
  390. #ifdef TEST_GEN
  391.     gen("1.in");
  392.     gen1("2.in");
  393.     gen2("3.in");
  394.     gen3("4.in");
  395.     gen4("5.in");
  396.     gen5("6.in");
  397. #endif // TEST_GEN
  398.  
  399.     return 0;
  400. }
  401.  
  402. // babbbbbb
  403.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.cpp:2:21: fatal error: testlib.h: No such file or directory
 #include "testlib.h"
                     ^
compilation terminated.
stdout
copy 
Standard output is empty
https://ideone.com/B96Kod
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!