Submission #50859

#TimeUsernameProblemLanguageResultExecution timeMemory
50859NicksechkoGift (IZhO18_nicegift)C++14
7 / 100
181 ms8452 KiB
//Solution by Zhusupov Nurlan #include <iostream> #include <sstream> #include <fstream> #include <string> #include <vector> #include <deque> #include <queue> #include <stack> #include <set> #include <map> #include <algorithm> #include <functional> #include <utility> #include <bitset> #include <cmath> #include <cstdlib> #include <ctime> #include <cstdio> #include <cstring> #include <climits> #include <string.h> #include <stdio.h> #include <assert.h> using namespace std; typedef long long LL; typedef map<string , int> MSI; typedef vector<int> VI; typedef pair<int, int> PII; #define endl '\n' #define pb(x) push_back(x) #define sqr(x) ((x) * (x)) #define F first #define S second #define SZ(t) ((int) t.size()) #define len(t) ((int) t.length()) #define base LL(1e9 + 7) #define fname "" #define sz 1000 * 1000 #define EPS (1e-8) #define INF ((int)1e9 + 9) #define mp make_pair LL mx, n, k, a[sz]; LL s; vector <pair <LL, LL> > b; vector <pair<LL, VI> > ans; int main() { // freopen(fname"in", "r", stdin); // freopen(fname"out", "w", stdout); ios_base::sync_with_stdio(false); cin.tie(0); cin >> n >> k; for (int i = 1; i <= n; i++) { cin >> a[i]; s += a[i]; mx = max(mx, a[i]); } if (s % k != 0 || mx > s / k) { cout << -1; return 0; } for (int q = 1; q <= 10; q++) { b.clear(); for (int i = 1; i <= n; i++) b.pb(mp(a[i], i)); int cnt; ans.clear(); LL ss = 0; random_shuffle(b.begin(), b.end()); while (ss <= s) { cnt = 0; LL mi = 1e18; VI p; if (rand() % 1000 == 0) random_shuffle(b.begin(), b.end()); if (b.size() < k) break; for (int i = 0; i < k; i++) { mi = min(mi, (b[i].F + 1) / 2); p.pb(b[i].S); } for (int i = k - 1; i >= 0; i--) { b[i].F -= mi; if (b[i].F == 0) { swap(b[i], b[b.size() - 1]); b.pop_back(); } } ans.pb(mp(mi, p)); ss += mi * k; } if (b.size() == 0) { cout << ans.size() << "\n"; for (int i = 0; i < ans.size(); i++) { cout << ans[i].F << " "; for (int j = 0; j < ans[i].S.size(); j++) cout << ans[i].S[j] << " "; cout << "\n"; } return 0; } } }

Compilation message (stderr)

nicegift.cpp: In function 'int main()':
nicegift.cpp:86:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       if (b.size() < k) break;
           ~~~~~~~~~^~~
nicegift.cpp:103:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int i = 0; i < ans.size(); i++) {
                       ~~^~~~~~~~~~~~
nicegift.cpp:105:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < ans[i].S.size(); j++)
                         ~~^~~~~~~~~~~~~~~~~
nicegift.cpp:76:9: warning: variable 'cnt' set but not used [-Wunused-but-set-variable]
     int cnt;
         ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...