Submission #1015559

#TimeUsernameProblemLanguageResultExecution timeMemory
1015559andrei_iorgulescuFortune Telling 2 (JOI14_fortune_telling2)C++14
0 / 100
6 ms6492 KiB
#include <bits/stdc++.h> using namespace std; int n,k,a[200005],b[200005],t[200005]; int g; bool tr[105][105]; vector<int> lol; int pa[200005],pb[200005]; pair<int,int> vv[400005]; int sp[200005]; void solve(vector<int> op) { set<int> ss; for (auto it : op) ss.insert(it); vector<int> vls; for (auto it : ss) vls.push_back(it); vls.push_back((int)2e9); int i0 = 0; for (int i = 1; i <= 2 * n; i++) { while (vls[i0] < vv[i].first) i0++; if (vv[i].second < 0) pb[-vv[i].second] = i0; else pa[vv[i].second] = i0; } for (int i = 0; i < vls.size(); i++) { for (int j = 0; j < vls.size(); j++) { int x0 = vls[i]; int x = vls[i],y = vls[j]; int cnt_swap = 0; for (auto it : op) { if (it >= x) swap(x,y),cnt_swap ^= 1; } if (cnt_swap) tr[i][j] = true; else tr[i][j] = false; } } for (int i = 1; i <= n; i++) { if ((!sp[i] and tr[pa[i]][pb[i]]) or (sp[i] and tr[pb[i]][pa[i]])) swap(a[i],b[i]),sp[i] ^= 1; } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n >> k; for (int i = 1; i <= n; i++) cin >> a[i] >> b[i]; for (int i = 1; i <= k; i++) cin >> t[i]; for (int i = 1; i <= n; i++) { vv[2 * i - 1] = {a[i],i}; vv[2 * i] = {b[i],-i}; } sort(vv + 1,vv + 2 * n + 1); g = 200; for (int i = 1; i <= k; i += g) { vector<int> op; for (int j = i; j <= k and j < i + g; j++) op.push_back(t[j]); solve(op); } long long ans = 0; for (int i = 1; i <= n; i++) ans += a[i]; cout << ans; return 0; }

Compilation message (stderr)

fortune_telling2.cpp: In function 'void solve(std::vector<int>)':
fortune_telling2.cpp:32:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for (int i = 0; i < vls.size(); i++)
      |                     ~~^~~~~~~~~~~~
fortune_telling2.cpp:34:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |         for (int j = 0; j < vls.size(); j++)
      |                         ~~^~~~~~~~~~~~
fortune_telling2.cpp:36:17: warning: unused variable 'x0' [-Wunused-variable]
   36 |             int x0 = vls[i];
      |                 ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...