Submission #129450

#TimeUsernameProblemLanguageResultExecution timeMemory
129450E869120Permutation Recovery (info1cup17_permutation)C++14
100 / 100
3203 ms4276 KiB
#include <iostream> #include <map> #include <set> #include <vector> #include <string> #include <algorithm> using namespace std; #pragma warning (disable: 4996) int cnta = 0, cntb = 0; // ------------------ LIBRARY -------------------- const long long mod = 4999999999999LL; const long long mod2 = 3777777777777LL; const int BACKET = 150; long long t[1 << 17], u[1 << 17], size_; long long X[1 << 13][BACKET + 9], sz[1 << 13]; bool used[1 << 17]; void init(vector<long long>E) { size_ = E.size() + 1; for (int i = 1; i <= E.size(); i++) { t[i] = E[i - 1]; X[i / BACKET][sz[i / BACKET]] = 131072LL * t[i] + 1LL * i; sz[i / BACKET] += 1; } for (int i = 0; i <= size_ / BACKET; i++) sort(X[i], X[i] + sz[i]); } void add_range(int l, int r, long long x) { int c = l / BACKET; for (int i = l; i < r; i++) { t[i] += x; if (t[i] >= mod) t[i] -= mod; } sz[c] = 0; for (int i = c * BACKET; i < (c + 1) * BACKET; i++) { if (used[i] == true || i <= 0 || i >= size_) continue; X[c][sz[c]] = 131072LL * t[i] + 1LL * i; sz[c]++; } sort(X[c], X[c] + sz[c]); } void add(int l, int r, long long x) { x = (x + mod) % mod; int c1 = l / BACKET, c2 = r / BACKET; if (c1 == c2) add_range(l, r, x); else { add_range(l, (c1 + 1) * BACKET, x); for (int i = c1 + 1; i <= c2; i++) { u[i] += x; if (u[i] >= mod) u[i] -= mod; } } } int get_minimum_id() { int id = -1; for (int i = size_ / BACKET; i >= 0; i--) { long long T = (mod + 1LL - u[i]); if (T >= mod) T -= mod; int pos1 = lower_bound(X[i], X[i] + sz[i], 131072LL * (T + 1LL)) - X[i]; pos1--; if (pos1 >= 0 && (X[i][pos1] >> 17) == T) { id = (X[i][pos1] & 131071LL); break; } } return id; } long long StringToMod(string S) { long long r = 0; for (int i = 0; i < S.size(); i++) { r *= 10LL; r += (long long)(S[i] - '0'); while (r >= mod) r -= mod; } return r; } long long N, A[1 << 18], S[1 << 18]; vector<long long>F; char cc[1 << 18]; int main() { cin >> N; for (int i = 1; i <= N; i++) { scanf("%s", &cc); string V = ""; for (int j = 0; j < 100000; j++) { if (cc[j] == 0) break; V += cc[j]; cc[j] = 0; } A[i] = StringToMod(V); } for (int i = N; i >= 1; i--) A[i] = (A[i] - A[i - 1] + mod) % mod; for (int i = 1; i <= N; i++) F.push_back(A[i]); init(F); for (int i = 1; i <= N; i++) { int pos1 = get_minimum_id(); S[pos1] = i; used[pos1] = true; add(pos1 + 1, N + 1, -A[pos1]); if (pos1 % BACKET == BACKET - 1) add_range(pos1, pos1, 0); } for (int i = 1; i <= N; i++) { if (i >= 2) printf(" "); printf("%d", S[i]); } printf("\n"); return 0; }

Compilation message (stderr)

permutation.cpp:8:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning (disable: 4996)
 
permutation.cpp: In function 'void init(std::vector<long long int>)':
permutation.cpp:24:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i <= E.size(); i++) {
                  ~~^~~~~~~~~~~
permutation.cpp: In function 'long long int StringToMod(std::__cxx11::string)':
permutation.cpp:71:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < S.size(); i++) {
                  ~~^~~~~~~~~~
permutation.cpp: In function 'int main()':
permutation.cpp:84:18: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[262144]' [-Wformat=]
   scanf("%s", &cc); string V = "";
               ~~~^
permutation.cpp:102:75: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
  for (int i = 1; i <= N; i++) { if (i >= 2) printf(" "); printf("%d", S[i]); } printf("\n");
                                                                       ~~~~^
permutation.cpp:84:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", &cc); string V = "";
   ~~~~~^~~~~~~~~~~
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...