codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1005.md (3526B)


      1 Source: https://codeforces.com/blog/entry/60511
      2 
      3 Tutorial is loading...
      4 
      5 **Code in C++ for details**
      6 
      7 ```
      8 int n;
      9 cin >> n;
     10 vector<int> a;
     11 int p = -1;
     12 forn(i, n) {
     13     int x;
     14     cin >> x;
     15     if (x == 1 && p != -1)
     16         a.push_back(p);
     17     p = x;    
     18 }
     19 a.push_back(p);
     20 cout << a.size() << endl;
     21 for (int i: a)
     22     cout << i << " ";
     23 ```
     24 
     25 Tutorial is loading...
     26 
     27 **Code in C++ for details**
     28 
     29 ```
     30 string s, t;
     31 cin >> s >> t;
     32 int w = 0;
     33 while (true) {
     34     int i = s.length() - w - 1;
     35     int j = t.length() - w - 1;
     36     if (i >= 0 && j >= 0 && s[i] == t[j])
     37         w++;
     38     else
     39         break;
     40 }
     41 cout << s.length() + t.length() - 2 * w << endl;
     42 ```
     43 
     44 Tutorial is loading...
     45 
     46 **Code in C++ for details**
     47 
     48 ```
     49 int n;
     50 cin >> n;
     51 vector<int> a(n);
     52 map<int,int> c;
     53 forn(i, n) {
     54     cin >> a[i];
     55     c[a[i]]++;
     56 }
     57 int ans = 0;
     58 forn(i, n) {
     59     bool ok = false;
     60     forn(j, 31) {
     61         int x = (1 << j) - a[i];
     62         if (c.count(x) && (c[x] > 1 || (c[x] == 1 && x != a[i])))
     63             ok = true;
     64     }
     65     if (!ok)
     66         ans++;
     67 }
     68 cout << ans << endl;
     69 ```
     70 
     71 Tutorial is loading...
     72 
     73 **Code in C++ for details**
     74 
     75 ```
     76 string s;
     77 cin >> s;
     78 int n = s.length();
     79 
     80 int r = 0;
     81 vector<int> fin(3, -1);
     82 fin[0] = 0;
     83 
     84 vector<int> z(n + 1);
     85 for (int i = 1; i <= n; i++) {
     86     r = (r + s[i - 1] - '0') % 3;
     87     z[i] = z[i - 1];
     88     if (fin[r] != -1)
     89         z[i] = max(z[i], z[fin[r]] + 1);
     90     fin[r] = i;
     91 }
     92 
     93 cout << z[n] << endl;
     94 ```
     95 
     96 Tutorial is loading...
     97 
     98 **Code in C++ for details**
     99 
    100 ```
    101 int n, m;
    102 cin >> n >> m;
    103 vector<int> p(n);
    104 forn(i, n)
    105     cin >> p[i];
    106 map<int,int> c;
    107 c[0] = 1;
    108 bool has = false;
    109 int sum = 0;
    110 long long ans = 0;
    111 for (int r = 0; r < n; r++) {
    112     if (p[r] < m)
    113         sum--;
    114     else if (p[r] > m)
    115         sum++;
    116 
    117     if (p[r] == m)
    118         has = true;
    119     if (has)
    120         ans += c[sum] + c[sum - 1];
    121     else
    122         c[sum]++;
    123 }
    124 cout << ans << endl;
    125 ```
    126 
    127 Tutorial is loading...
    128 
    129 **Code in C++ for details**
    130 
    131 ```
    132 long long greaterCount(int m) {
    133     vector<int> s(2 * n + 1);
    134     int sum = n;
    135     long long result = 0;
    136     s[sum] = 1;
    137     long long add = 0;
    138     forn(i, n) {
    139         if (a[i] < m)
    140             sum--, add -= s[sum];
    141         else
    142             add += s[sum], sum++;
    143         result += add;
    144         s[sum]++;
    145     }
    146     return result;
    147 }
    148 
    149 cin >> n >> m;
    150 a = vector<int>(n);
    151 forn(i, n)
    152     cin >> a[i];
    153 cout << greaterCount(m) - greaterCount(m + 1) << endl;
    154 ```
    155 
    156 Tutorial is loading...
    157 
    158 **Code in C++ for details**
    159 
    160 ```
    161 int n, m, k;
    162 cin >> n >> m >> k;
    163 vector<vector<int>> g(n);
    164 vector<int> a(m), b(m);
    165 forn(i, m) {
    166     cin >> a[i] >> b[i];
    167     a[i]--, b[i]--;
    168     g[a[i]].push_back(b[i]);
    169     g[b[i]].push_back(a[i]);
    170 }
    171 
    172 queue<int> q;
    173 q.push(0);
    174 vector<int> d(n, INT_MAX);
    175 d[0] = 0;
    176 
    177 while (!q.empty()) {
    178     int u = q.front();
    179     q.pop();
    180     for (int v: g[u])
    181         if (d[v] == INT_MAX) {
    182             d[v] = d[u] + 1;
    183             q.push(v);
    184         }
    185 }
    186 
    187 vector<vector<int>> inc(n);
    188 forn(i, m) {
    189     if (d[a[i]] + 1 == d[b[i]])
    190         inc[b[i]].push_back(i);
    191     if (d[b[i]] + 1 == d[a[i]])
    192         inc[a[i]].push_back(i);
    193 }
    194 
    195 vector<int> f(n);
    196 vector<string> result;
    197 
    198 forn(i, k) {
    199     string s(m, '0');
    200     for (int j = 1; j < n; j++)
    201         s[inc[j][f[j]]] = '1';
    202     result.push_back(s);
    203 
    204     bool ok = false;
    205     for (int j = 1; j < n; j++)
    206         if (f[j] + 1 < inc[j].size()) {
    207             ok = true;
    208             f[j]++;
    209             break;
    210         } else
    211             f[j] = 0;
    212     if (!ok)
    213         break;
    214 }
    215 
    216 cout << result.size() << endl;
    217 forn(i, result.size())
    218     cout << result[i] << endl;
    219 ```