Submission #1332259

#	Time	Username	Problem	Language	Result	Execution time	Memory
1332259		hauserl	A String Problem (EGOI25_stringproblem)	C++20	0 / 100	3 ms	1604 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define f first
#define s second
using namespace std;

int main() {

    ll N; scanf("%d",&N);
    ll TN = N*2;

    vector<pair<ll, ll>> strings(N);
    vector<ll> circle(2*N);

    for (ll i = 0; i < N; i++) {
        ll a,b; scanf("%lld %lld",&a, &b);
        strings[i] = {a,b};
        circle[a] = i;
        circle[b] = i;
    }

    ll maxParallelCount = LONG_LONG_MIN;
    ll bAxis = 1;
    vector<ll> counts(TN,0); // axis


    for (ll i = 0; i < TN; i++) {
        // ein pin gerade einer ungerade -> sonst falsch
        ll P1 = strings[i].f;
        ll P2 = strings[i].s;
        if ((P1+P2)%2 != 1) continue;

        // ll axis = ((min(P1, P2) + (max(P1, P2) - min(P1, P2))/2)) % N;
        ll axis = (P1 + P2) % TN;

        if (axis%2 != 1) continue;

        counts[axis]++;

        if (counts[axis] > maxParallelCount) {
            maxParallelCount = counts[axis];
            bAxis = axis;
        }
    }


    // immer irgendwo bei nicht parallelen anfangen und die lücke die entsteht mit dem gegenüber füllen
    vector<tuple<ll, ll, ll>> moves;
    vector<bool> doneString(N);
    vector<bool> donePin(2*N);

    for (ll i = 0; i < 2*N; i++) {
        ll string = circle[i];

        if (doneString[string] || donePin[i]) continue;


        doneString[string] = true;
        
        // ll second = (((bAxis + 1) % TN - (i - bAxis)) + TN) % TN;
        ll second = (bAxis - i + TN ) % TN;
        
        ll prevSecond = strings[string].f == i ? strings[string].s : strings[string].f;

        if (second == prevSecond) {
            doneString[string] = true;
            donePin[i] = true;
            donePin[second] = true;
            continue;
        }

        moves.push_back({string, prevSecond, second});

        donePin[i] = true;
        donePin[second] = true;


        // ll oppositePrevSecond = (((bAxis + 1) % TN - (prevSecond - bAxis)) + TN) % TN;
        ll oppositePrevSecond = (bAxis - prevSecond + TN) %TN;
        
        ll string2 = circle[oppositePrevSecond];

        while (!doneString[string2]) {
            doneString[string2]= true;

            second = prevSecond;

            prevSecond = strings[string2].f == oppositePrevSecond ? strings[string2].s : strings[string2].f;

            moves.push_back({string2, prevSecond, second});

            donePin[second] = true;
            donePin[oppositePrevSecond] = true;

            
            // oppositePrevSecond = (((bAxis + 1) % TN - (prevSecond - bAxis)) + TN) % TN;
            oppositePrevSecond = (bAxis - prevSecond + TN) %TN;
            if (oppositePrevSecond == prevSecond) oppositePrevSecond++;
            oppositePrevSecond %= TN;
            string2 = circle[oppositePrevSecond];
        }
               
    }


    printf("%lld \n", moves.size());
    for (ll i = 0; i < moves.size(); i++) {
        printf("%lld %lld %lld\n", get<0>(moves[i]), get<1>(moves[i]), get<2>(moves[i]));
    }

    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:9:19: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
    9 |     ll N; scanf("%d",&N);
      |                  ~^  ~~
      |                   |  |
      |                   |  long long int*
      |                   int*
      |                  %lld
Main.cpp:106:16: warning: format '%lld' expects argument of type 'long long int', but argument 2 has type 'std::vector<std::tuple<long long int, long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wformat=]
  106 |     printf("%lld \n", moves.size());
      |             ~~~^      ~~~~~~~~~~~~
      |                |                |
      |                long long int    std::vector<std::tuple<long long int, long long int, long long int> >::size_type {aka long unsigned int}
      |             %ld
Main.cpp:9:16: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 |     ll N; scanf("%d",&N);
      |           ~~~~~^~~~~~~~~
Main.cpp:16:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |         ll a,b; scanf("%lld %lld",&a, &b);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 0
• Subtask 2: 0 / 14
• Subtask 3: 0 / 16
• Subtask 4: 0 / 12
• Subtask 5: 0 / 28
• Subtask 6: 0 / 30