제출 #197334

#제출 시각아이디문제언어결과실행 시간메모리
197334PankinHidden Sequence (info1cup18_hidden)C++14
0 / 100
82 ms380 KiB
#include<bits/stdc++.h> #include "grader.h" /* #pragma GCC optimize("unroll-loops") #pragma GCC optimize("Ofast") #pragma GCC optimize("-O3") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") */ #define mp make_pair #define ll long long #define ld long double #define pb push_back #define fast_io ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define fs first #define sc second #define getfiles ifstream cin("input.txt"); ofstream cout("output.txt"); #define endl '\n' #define pii pair<int, int> const int INF = 2000000005; const ll BIG_INF = 2000000000000000005; const int mod = 1000000007; const int P = 31; const ld PI = 3.141592653589793238462643; const double eps = 1e-9; using namespace std; bool valid(int x, int y, int n, int m) { return x >= 0 && y >= 0 && x < n && y < m; } mt19937 rng(1999999973); map<int, bool> fin; inline pii getBlock(int num, vector<int> &ans) { int cur = 0, l; for (int i = 0; ; i++) { if (i == ans.size()) return mp(-1, -1); if (i != 0 && ans[i] != ans[i - 1]) cur++; if (cur == num) { l = i; break; } } int r = l; while(r + 1 < ans.size() && ans[r + 1] == ans[l]) r++; return mp(l, r); } inline void doBlock(int i, vector<int> &ans, int &ad, int &n, int l, int r) { int cursize = getBlock(i, ans).sc - getBlock(i, ans).fs + 1; vector<int> cur; int curBlock = 0; cur.pb(ans[0]); if (i != 0) { cur.pop_back(); curBlock++; cur.pb(ans[getBlock(1, ans).fs]); } while(curBlock != i) { pii otr = getBlock(curBlock, ans); if (curBlock + 2 <= i && otr.fs == otr.sc) { cur.pb(ans[otr.fs]); curBlock += 2; continue; } else { cur.pb(ans[otr.sc + 1]); curBlock++; continue; } } int val = ans[getBlock(curBlock, ans).fs]; for (int i = 0; i < cursize; i++) cur.pb(val); curBlock++; if (getBlock(curBlock, ans) != mp(-1, -1)) cur.pb(val ^ 1); while(getBlock(curBlock + 1, ans) != mp(-1, -1)) { pii otr = getBlock(curBlock, ans); if (getBlock(curBlock + 2, ans) != mp(-1, -1) && otr.fs == otr.sc) { cur.pb(ans[otr.fs]); curBlock += 2; continue; } else { cur.pb(ans[otr.sc + 1]); curBlock++; continue; } } if (cur.size() > n / 2 + 3) { return; } if (!isSubsequence(cur)) { fin[i] = true; return; } ans.insert(ans.begin() + l, ans[r]); ad++; doBlock(i, ans, ad, n, l, r + 1); } vector<int> findSequence(int n) { int sw = 0, col = -1; for (int i = 0; i <= n / 2 + 1; i++) { vector<int> seq; for (int j = 0; j < i; j++) seq.pb(0); if (!isSubsequence(seq)) { col = i - 1; break; } } if (col == -1) { sw = 1; for (int i = 0; i <= n / 2 + 1; i++) { vector<int> seq; for (int j = 0; j < i; j++) seq.pb(1); if (!isSubsequence(seq)) { col = i - 1; break; } } } vector<int> ans, cur; if (col == 0) { for (int i = 0; i < n; i++) { ans.pb(sw ^ 1); } return ans; } for (int i = 0; i < col; i++) ans.pb(sw); cur = ans; int ad = 0; for (int i = 0; i <= col; i++) { cur.insert(cur.begin() + i, 1 ^ sw); if (isSubsequence(cur)) { ans.insert(ans.begin() + i + ad, 1 ^ sw); ad++; } cur.erase(cur.begin() + i); } cur.clear(); for (int i = 0; getBlock(i, ans) != mp(-1, -1); i++) { pii co = getBlock(i, ans); int l = co.fs, r = co.sc; if (ans[l] == sw) continue; doBlock(i, ans, ad, n, l, r); } for (int i = 0; getBlock(i, ans) != mp(-1, -1); i++) { pii co = getBlock(i, ans); int l = co.fs, r = co.sc; if (ans[l] == sw) continue; if (fin[i]) continue; for (int j = 0; j < n - col - ad; j++) ans.insert(ans.begin() + l, sw ^ 1); break; } return ans; }

컴파일 시 표준 에러 (stderr) 메시지

hidden.cpp: In function 'std::pair<int, int> getBlock(int, std::vector<int>&)':
hidden.cpp:42:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (i == ans.size())
             ~~^~~~~~~~~~~~~
hidden.cpp:52:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(r + 1 < ans.size() && ans[r + 1] == ans[l])
           ~~~~~~^~~~~~~~~~~~
hidden.cpp: In function 'void doBlock(int, std::vector<int>&, int&, int&, int, int)':
hidden.cpp:106:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (cur.size() > n / 2 + 3) {
         ~~~~~~~~~~~^~~~~~~~~~~
hidden.cpp: In function 'std::vector<int> findSequence(int)':
hidden.cpp:175:24: warning: unused variable 'r' [-Wunused-variable]
         int l = co.fs, r = co.sc;
                        ^
grader.cpp: In function 'int main()':
grader.cpp:28:43: warning: format '%d' expects argument of type 'int', but argument 3 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
     fprintf (fifo_out, "%d\n", ans.size ());
                                ~~~~~~~~~~~^
grader.cpp:29:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0; i<ans.size () && i < N; i++)
                   ~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...