Submission #640673

#TimeUsernameProblemLanguageResultExecution timeMemory
640673SanguineChameleonZagonetka (COI18_zagonetka)C++14
100 / 100
93 ms336 KiB
// BEGIN BOILERPLATE CODE #include <bits/stdc++.h> using namespace std; #ifdef KAMIRULEZ const bool kami_loc = true; const long long kami_seed = 69420; #else const bool kami_loc = false; const long long kami_seed = chrono::steady_clock::now().time_since_epoch().count(); #endif const string kami_fi = "kamirulez.inp"; const string kami_fo = "kamirulez.out"; mt19937_64 kami_gen(kami_seed); long long rand_range(long long rmin, long long rmax) { uniform_int_distribution<long long> rdist(rmin, rmax); return rdist(kami_gen); } void file_io(string fi, string fo) { if (fi != "" && (!kami_loc || fi == kami_fi)) { freopen(fi.c_str(), "r", stdin); } if (fo != "" && (!kami_loc || fo == kami_fo)) { freopen(fo.c_str(), "w", stdout); } } void set_up() { if (kami_loc) { file_io(kami_fi, kami_fo); } ios_base::sync_with_stdio(0); cin.tie(0); } void just_do_it(); void just_exec_it() { if (kami_loc) { auto pstart = chrono::steady_clock::now(); just_do_it(); auto pend = chrono::steady_clock::now(); long long ptime = chrono::duration_cast<chrono::milliseconds>(pend - pstart).count(); string bar(50, '='); cout << '\n' << bar << '\n'; cout << "Time: " << ptime << " ms" << '\n'; } else { just_do_it(); } } int main() { set_up(); just_exec_it(); return 0; } // END BOILERPLATE CODE // BEGIN MAIN CODE const int ms = 1e2 + 20; int a[ms]; int b[ms]; int c[ms]; int q[ms]; int p[ms]; bool g[ms]; vector<int> adj1[ms]; vector<int> adj2[ms]; vector<int> adj3[ms]; int dzi[ms]; int dzo[ms]; int mi[ms]; int ma[ms]; int lt, rt; map<pair<int, int>, bool> e; vector<int> pp; void dfs(int u) { g[u] = true; for (auto v: adj1[u]) { if (!g[v] && lt <= v && v <= rt) { dfs(v); } } pp.push_back(u); } bool check() { for (auto x: e) { if (q[x.first.first] > q[x.first.second]) { return false; } } return true; } void just_do_it() { int n; cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; p[a[i]] = i; } for (int i = 1; i <= n - 1; i++) { for (int j = 1; j + i <= n; j++) { lt = j; rt = j + i; pp.clear(); for (int k = lt; k <= rt; k++) { g[k] = false; } dfs(rt); if (g[lt]) { continue; } for (int k = lt; k <= rt; k++) { if (!g[k]) { dfs(k); } } for (int i = 1; i <= lt - 1; i++) { b[i] = i; } for (int i = rt + 1; i <= n; i++) { b[i] = i; } for (int i = 0; i < (int)pp.size(); i++) { b[pp[i]] = lt + i; } for (int i = 1; i <= n; i++) { q[i] = b[a[i]]; } cout << "query"; for (int i = 1; i <= n; i++) { cout << " " << q[i]; } cout << endl; int d; cin >> d; if (d == 0) { adj2[p[lt]].push_back(p[rt]); adj3[p[rt]].push_back(p[lt]); dzo[p[lt]]++; dzi[p[rt]]++; adj1[rt].push_back(lt); } } } set<int, greater<int>> s; for (int i = 1; i <= n; i++) { if (dzo[i] == 0) { s.insert(i); } } for (int i = n; i >= 1; i--) { int u = *s.begin(); mi[u] = i; s.erase(u); for (auto v: adj3[u]) { dzo[v]--; if (dzo[v] == 0) { s.insert(v); } } } for (int i = 1; i <= n; i++) { if (dzi[i] == 0) { s.insert(i); } } for (int i = 1; i <= n; i++) { int u = *s.begin(); ma[u] = i; s.erase(u); for (auto v: adj2[u]) { dzi[v]--; if (dzi[v] == 0) { s.insert(v); } } } cout << "end" << endl; for (int i = 1; i <= n - 1; i++) { cout << mi[i] << " "; } cout << mi[n]; cout << endl; for (int i = 1; i <= n - 1; i++) { cout << ma[i] << " "; } cout << ma[n]; cout << endl; } // END MAIN CODE

Compilation message (stderr)

zagonetka.cpp: In function 'void file_io(std::string, std::string)':
zagonetka.cpp:25:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |   freopen(fi.c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
zagonetka.cpp:28:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |   freopen(fo.c_str(), "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...